You are given two arrays a and b, both of length n.
Let's define a function f(l,r)=∑ai⋅bi. (l≤i≤r)
Your task is to reorder the elements (choose an arbitrary order of elements) of the array b to minimize the value of ∑f(l,r). (1≤l≤r≤n) 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.
The first line of the input contains one integer n (1≤n≤2⋅10^5) — the number of elements in a and b.
The second line of the input contains n integers a1,a2,…,an (1≤ai≤10^6), where ai is the i-th element of a.
The third line of the input contains n integers b1,b2,…,bn (1≤bj≤10^6), where bj is the j-th element of b.
Print one integer — the minimum possible value of ∑f(l,r) ( 1≤l≤r≤n) after rearranging elements of b, taken modulo 998244353. Note that you should minimize the answer but not its remainder.
5 1 8 7 2 4 9 7 2 9 3
646
1 1000000 1000000
757402647
2 1 3 4 2
20hint: f(1,1)=4 f(2,2)=6 f(1,2)=10 4+6+10=20