You are given two arrays $a$ and $b$, both of length $n$.

Let's define a function $f(l, r) = \sum\limits_{l \le i \le r} a_i \cdot b_i$.

Your task is to reorder the elements (choose an arbitrary order of elements) of the array $b$ to minimize the value of $\sum\limits_{1 \le l \le r \le n} f(l, r)$. Since the answer can be very large, you have to print it modulo $998244353$. Note that you should minimize the answer but not its remainder.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in $a$ and $b$.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$), where $a_i$ is the $i$-th element of $a$.

The third line of the input contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_j \le 10^6$), where $b_j$ is the $j$-th element of $b$.


-----Output-----

Print one integer — the minimum possible value of $\sum\limits_{1 \le l \le r \le n} f(l, r)$ after rearranging elements of $b$, taken modulo $998244353$. Note that you should minimize the answer but not its remainder.


-----Examples-----
Input
5
1 8 7 2 4
9 7 2 9 3

Output
646

Input
1
1000000
1000000

Output
757402647

Input
2
1 3
4 2

Output
20
[{"code": "n = int(input())\n\na = list(map(int, input().split()))\naord = sorted([i for i in range(n)], key=lambda x: a[x] * (n - x) * (x + 1))\n\nb = sorted(map(int, input().split()))[::-1]\nnew_b = [0] * n\nfor i in range(n):\n    new_b[aord[i]] = b[i]\nb = new_b\n\nm = 998244353\n\nc = [0] * n\nfor i in range(n):\n    c[i] = a[i] * b[i] % m\n\nans = 0\nfor i in range(n):\n    u = c[i] * (n - i) * (i + 1) % m\n    ans = (ans + u) % m\nprint(ans)\n", "passed": true, "time": 0.3, "memory": 14140.0, "status": "done"}, {"code": "n = int(input())\na = list(map(int, input().split()))\nb = list(map(int, input().split()))\n\ncount = []\nfor i in range(n):\n    count.append((n-i)*(i+1)*a[i])\nb.sort()\ncount.sort(reverse = True)\nans = 0\nfor i in range(n):\n\n    ans += count[i]*b[i]\n    ans %= 998244353\nprint(ans)\n", "passed": true, "time": 0.15, "memory": 14216.0, "status": "done"}, {"code": "MOD = 998244353\nn = int(input())\na = [*map(int, input().split())]\nb = [*map(int, input().split())]\nfor i in range(n):\n    a[i] = (a[i] * (n - i) * (i + 1))\na.sort(reverse = True)\nb.sort()\nres = 0\nfor i in range(n):\n    a[i] %= MOD\n    res += (a[i] * b[i]) % MOD\n    res %= MOD\nprint(res)", "passed": true, "time": 0.21, "memory": 14060.0, "status": "done"}, {"code": "n = int(input())\na = list(map(int, input().split()))\nb = list(map(int, input().split()))\nfor i in range(n):\n\ta[i] = a[i] * (i + 1) * (n - i)\na = sorted(a)\nb = sorted(b)\nans = 0\nfor i in range(n):\n\tans += b[n - i - 1] * a[i] % 998244353\n\tans %= 998244353\nprint(ans)\n", "passed": true, "time": 0.18, "memory": 14096.0, "status": "done"}, {"code": "def main():\n    n = int(input())\n    mod = 998244353\n    a = list(map(int, input().split()))\n    b = sorted(map(int, input().split()))\n    for i in range(n):\n        a[i] *= (i + 1) * (n - i)\n    a.sort(reverse = 1)\n    ans = 0\n    for i in range(n):\n        ans = (ans + a[i] * b[i]) % mod\n    print(ans)\n    \n    return 0\n\nmain()", "passed": true, "time": 0.14, "memory": 14056.0, "status": "done"}, {"code": "n=int(input())\nA=list(map(int,input().split()))\nB=list(map(int,input().split()))\nmod=998244353\n\nAX=[]\n\nfor i in range(n):\n    AX.append(A[i]*(i+1)*(n-i))\n\nAX.sort()\nB.sort(reverse=True)\n\nANS=0\nfor i in range(n):\n    ANS=(ANS+AX[i]*B[i])%mod\n\nprint(ANS)\n", "passed": true, "time": 0.19, "memory": 14120.0, "status": "done"}, {"code": "n = int(input())\nA = list(map(int, input().split()))\nB = list(map(int, input().split()))\nfor i in range(n):\n    A[i] *= (i + 1) * (n - i)\nA.sort()\nB.sort(reverse=True)\nC = []\ncnt = 0\nM = 998244353\nfor i in range(n):\n    cnt += A[i] * B[i]\n    cnt %= M\nprint(cnt)\n", "passed": true, "time": 0.29, "memory": 14232.0, "status": "done"}, {"code": "def getN():\n    return int(input())\ndef getList():\n    return list(map(int, input().split()))\nMOD = 998244353\n\nn = getN()\nanums = getList()\nbnums = getList()\nanums = [a * (i+1) * (n-i) for i, a in enumerate(anums)]\nanums.sort()\nbnums.sort(reverse=True)\nans = 0\nfor a, b in zip(anums, bnums):\n    ans += a * b\n    ans = ans % MOD\n\nprint(ans)", "passed": true, "time": 0.14, "memory": 14136.0, "status": "done"}, {"code": "n=int(input())\na=[int(x) for x in input().split()]\nb=[int(x) for x in input().split()]\ncounter=0\nb.sort(reverse=True)\nc=[]\nfor i in range(n):\n    c.append(a[i]*b[i])\ntot=[]\nfor i in range(n):\n    x=(min(i,n-i-1)+1)\n    tot.append((x*(x+1)+(n-2*x)*x)*a[i])\ntot.sort()\nfor i in range(n):\n    counter+=tot[i]*b[i]\n    \nprint(counter%998244353)\n", "passed": true, "time": 0.14, "memory": 14304.0, "status": "done"}, {"code": "n = int(input())\na = list(map(int, input().split()))\na1 = sorted([a[i] * (n - i) * (i + 1) for i in range(n)])\nb = sorted(list(map(int, input().split())), key=lambda x: -x)\nans = 0\nc = 998244353\nfor i in range(n):\n    ans = (ans + a1[i] * b[i]) % c\nprint(ans)\n", "passed": true, "time": 0.19, "memory": 14244.0, "status": "done"}, {"code": "n = int(input())\na = list(map(int, input().split()))\nb = list(map(int, input().split()))\nc = []\nfor i in range(n):\n    c.append(a[i] * (n - i) * (i + 1))\nc.sort()\nb.sort(reverse=True)\nans = 0\nfor i in range(n):\n    ans = (ans + c[i] * b[i]) % 998244353\nprint(ans)", "passed": true, "time": 0.27, "memory": 14256.0, "status": "done"}, {"code": "n=int(input())\na=[int(s) for s in input().split()]\nb=[int(s) for s in input().split()]\nans=0\nb.sort()\nfor i in range(n):\n    k=(i+1)*(n-i)\n    a[i]*=k\na.sort()\nfor i in range(n):\n    ans+=b[n-i-1]*a[i]\n    ans%=998244353\nprint(ans)", "passed": true, "time": 0.19, "memory": 14088.0, "status": "done"}, {"code": "n = int(input())\na = list(map(int, input().split()))\nb = list(map(int, input().split()))\na = [0] + a\nb = [0] + b\n# print(n, a, b)\nfor i in range(1, n+1) :\n    a[i] *= i\n    a[i] *= n+1-i\na.sort()\nb.sort()\n# print(n, a, b)\nans = 0\nmod = 998244353\nfor i in range(1, 1+n) :\n    ans += ( a[i] * b[n+1-i] ) % mod\n    if ans >= mod : ans -= mod\nprint(ans)\n", "passed": true, "time": 0.14, "memory": 14108.0, "status": "done"}, {"code": "# AC\nimport sys\n\n\nclass Main:\n    def __init__(self):\n        self.buff = None\n        self.index = 0\n\n    def __next__(self):\n        if self.buff is None or self.index == len(self.buff):\n            self.buff = self.next_line()\n            self.index = 0\n        val = self.buff[self.index]\n        self.index += 1\n        return val\n\n    def next_line(self):\n        return sys.stdin.readline().split()\n\n    def next_ints(self):\n        return [int(x) for x in sys.stdin.readline().split()]\n\n    def next_int(self):\n        return int(next(self))\n\n    def solve(self):\n        n = self.next_int()\n        a = self.next_ints()\n        b = sorted(self.next_ints())[::-1]\n        for i in range(0, n):\n            mm = (i + 1) * (n - i)\n            a[i] *= mm\n        a = sorted(a)\n        mod = 998244353\n        c = [a[i] * b[i] % mod for i in range(0, n)]\n        print(sum(c) % mod)\n\n\ndef __starting_point():\n    Main().solve()\n\n__starting_point()", "passed": true, "time": 0.15, "memory": 14172.0, "status": "done"}, {"code": "n = int(input())\na = [[q*(n-q1)*(q1+1), q1] for q1, q in enumerate(list(map(int, input().split())))]\ns = sorted(list(map(int, input().split())), reverse=True)\nd = sorted(a)\nans = [0]*len(s)\nfor q in range(n):\n    ans[d[q][1]] = s[q]\nprint(sum(a[q][0]*ans[q] for q in range(n)) % 998244353)\n", "passed": true, "time": 0.14, "memory": 14216.0, "status": "done"}, {"code": "from sys import stdin, stdout\n\nMOD = 998244353\n\ndef __starting_point():\n    n = int(stdin.readline())\n    A = [int(x) for x in stdin.readline().rstrip().split()]\n    B = [int(x) for x in stdin.readline().rstrip().split()]\n\n    for i, a in enumerate(A):\n        A[i] *= (i+1)*(n-i)\n\n    A.sort(reverse = True)\n    B.sort()\n\n    res = 0\n    for a, b in zip(A, B):\n        res += a * b\n        res %= MOD\n    \n    print(res)\n\n__starting_point()", "passed": true, "time": 0.14, "memory": 14128.0, "status": "done"}, {"code": "n = int(input())\na = list(map(int,input().split()))\nb = list(map(int,input().split()))\nmn = [a[i] * (i + 1) * (n - i) for i in range(n)]\nmn.sort()\nb.sort()\nb.reverse()\nwyn = 0\nfor i in range(n):\n\twyn = (wyn + b[i] * mn[i]) % 998244353\nprint(wyn)", "passed": true, "time": 0.14, "memory": 14200.0, "status": "done"}, {"code": "n=int(input())\na=list(map(int,input().split()))\nb=sorted(list(map(int,input().split())),reverse=True)\n\nans=0\n\nmmm=998244353\n\nc=sorted([a[i]*(i+1)*(n-i) for i in range(n)])\n\nfor i in range(n):\n    ans=(ans+c[i]*b[i])%mmm\n\nprint(ans)\n", "passed": true, "time": 0.14, "memory": 14248.0, "status": "done"}, {"code": "R = lambda: map(int, input().split())\n\nm = 998244353\nn = int(input())\na = list(R())\nb = list(R())\nfor i in range(n): a[i] *= (i+1)*(n-i)\na.sort()\nb.sort(reverse=True)\nprint(sum([x*y%m for x,y in zip(a, b)]) % m)", "passed": true, "time": 0.14, "memory": 14212.0, "status": "done"}, {"code": "n = int(input())\nar = list(map(int, input().split()))\nbr = list(map(int, input().split()))\n\nMOD = 998244353\n\nfor i in range(n):\n    ar[i] *= (i + 1) * (n - i)\n\nar = sorted(ar)\nbr = sorted(br)\n\nans = 0\n\nfor i in range(n):\n    ans = (ans + ar[i] * br[n - i - 1]) % MOD\n\nprint(ans)\n \n", "passed": true, "time": 0.14, "memory": 14276.0, "status": "done"}, {"code": "N = int(input())\nA = list(map(int, input().split()))\nB = list(map(int, input().split()))\n\nfor i in range(N):\n\tA[i] = A[i]*(i+1)*(N-i)\n\nA.sort()\nB.sort()\n\nans = 0\nfor i in range(N):\n\tans = ans + (A[i]*B[N-i-1])%998244353\n\nprint(ans%998244353)\n", "passed": true, "time": 0.14, "memory": 14276.0, "status": "done"}, {"code": "IN = input\nrint = lambda: int(IN())\nrmint = lambda: map(int, IN().split())\nrlist = lambda: list(rmint())\n\nn = rint()\na = rlist()\nb = rlist()\nb.sort()\nb.reverse()\nfor i in range(n):\n    a[i] *= (i + 1) * (n - i)\na.sort()\nans = 0\nfor i in range(n):\n    ans += b[i] * a[i]\n    ans %= 998244353\nprint(ans)", "passed": true, "time": 0.14, "memory": 14076.0, "status": "done"}, {"code": "N = int(input())\nA = [int(a) for a in input().split()]\nB = sorted([int(a) for a in input().split()])[::-1]\n\nAA = []\nfor i in range(N):\n    AA.append(A[i]*(i+1)*(N-i))\n\nAA = sorted(AA)\n\nprint(sum([B[i]*AA[i] for i in range(N)]) % 998244353)\n", "passed": true, "time": 0.13, "memory": 14084.0, "status": "done"}]