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

Let's define a function f(l, r) = ∑_{l ≤ i ≤ r} a_i ⋅ b_i.

Your task is to reorder the elements (choose an arbitrary order of elements) of the array b to minimize the value of ∑_{1 ≤ l ≤ r ≤ 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 ≤ n ≤ 2 ⋅ 10^5) — the number of elements in a and b.

The second line of the input contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 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, ..., b_n (1 ≤ b_j ≤ 10^6), where b_j is the j-th element of b.

Output

Print one integer — the minimum possible value of ∑_{1 ≤ l ≤ r ≤ 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
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        new Main().run();}

        void solve(){

         int n = ni();
         long a[] = nal(n);
         long b[] = nal(n);

         long p[] =new long[n];
         for(int i=0;i<n;++i){
             int left = i+1;
             int right = n-i;
             long cur = a[i]*left*right;
             p[i] = cur;
         }
         Arrays.sort(p);

         Arrays.sort(b);
        long s = 0;
         for(int i=0;i<n;++i){
             s += p[i]*b[n-1-i];
             s %= 998244353;
         }
         println(s);




//         PriorityQueue<int[]> q= new PriorityQueue<>((x,y)->{return x[0]-y[0];});
//
//         q.offer(new int[]{0,0});
//         boolean inq[] = new boolean[n];
//         while(q.size()>0){
//             int c[]= q.poll();
//             for(int i=h[c[1]];i!=-1;i=ne[i]){
//                 if(!inq[to[i]]) {
//                     q.offer(new int[]{ wt[i], to[i]});
//                     inq[to[i]] = true;
//                 }
//             }
//         }





        }


       int err = 0;
    long dfs(int rt,int remain,long res[][],int dp[],int k,long p,int [][]vis1){
        if(res[rt][remain]!=0){
            return res[rt][remain];
        }
        vis1[rt][remain] = 1;
        int cur = dp[rt] + remain;
        for(int i=h1[rt];i!=-1;i=ne1[i]){
            int nz = cur-wt1[i]-dp[to1[i]];
            if(nz<0) continue;
            if(nz<=k) {
                if(vis1[to1[i]][nz]==1){
                    err = 1;
                }
                res[rt][remain] += dfs(to1[i], nz,res,dp,k,p,vis1);
                res[rt][remain] %= p;
            }
        }
        vis1[rt][remain] = 0;
        return res[rt][remain];
    }



    int ct = 0;
    void add(int u,int v,int w){
        to[ct] = v;
        wt[ct] = w;
        ne[ct] = h[u];
        h[u] = ct;

        to1[ct] = u;
        wt1[ct] = w;
        ne1[ct] = h1[v];
        h1[v] = ct++;
    }
    int []h,ne,to,wt,h1,ne1,to1,wt1;
    void solve11() {

        int t = ni();

        mb:for(int o=0;o<t;++o) {
            ct = 0;
            int n = ni();
            int m = ni();
            int k = ni();
            long p = nl();
            h = new int[n];
            Arrays.fill(h, -1);
            to = new int[m];
            ne = new int[m];
            wt = new int[m];

            h1 = new int[n];
            Arrays.fill(h1, -1);
            to1 = new int[m];
            ne1 = new int[m];
            wt1 = new int[m];

            for (int i = 0; i < m; ++i) {
                int u = ni() - 1;
                int v = ni() - 1;
                int w = ni();
                add(u, v, w);
            }
            int dp[] = new int[n];
            Arrays.fill(dp, 1000000000);
            dp[0] = 0;
            PriorityQueue<int[]> q = new PriorityQueue<>((x, y) -> {
                return x[0] - y[0];
            });
            q.offer(new int[]{0,0});
            while (q.size() > 0) {
                int c[] = q.poll();
                if (c[0] > dp[c[1]]) continue;
                for (int i = h[c[1]]; i != -1; i = ne[i]) {
                    if (c[0] + wt[i] < dp[to[i]]) {
                        dp[to[i]] = c[0] + wt[i];
                        q.offer(new int[]{dp[to[i]], to[i]});
                    }
                }
            }



            int dp1[] = new int[n];
            Arrays.fill(dp1, 1000000000);
            dp1[n-1] = 0;
            q.offer(new int[]{0,n-1});
            while (q.size() > 0) {
                int c[] = q.poll();
                if (c[0] > dp1[c[1]]) continue;
                for (int i = h1[c[1]]; i != -1; i = ne1[i]) {
                    if (c[0] + wt1[i] < dp1[to1[i]]) {
                        dp1[to1[i]] = c[0] + wt1[i];
                        q.offer(new int[]{dp1[to1[i]], to1[i]});
                    }
                }
            }










//            if(k==0) {
//                println(res[n - 1]);continue ;
//            }
            int stk[] = new int[2*n];
            int pt = 0;
            int instk[] = new int[2*n];
            int qt = 0;
            int vis[] = new int[n];
            stk[pt++] = 0;
            while (pt > 0) {
                int c = stk[--pt];
                if (c >= 0) {
                    stk[pt++] = ~c;
                    instk[qt++] = c;
                    vis[c] = 1;
                    ot:
                    for (int i = h[c]; i != -1; i = ne[i]) {
                        if (vis[to[i]] == 0) {
                            stk[pt++] = to[i];
                        } else if (vis[to[i]] == 1 && dp[to[i]] == dp[c] && dp[c]+dp1[c]==dp[n-1]) {
                            int ck = dp[c];
                            int from = qt - 1;
                            while (instk[from] != to[i]&& from>=0) {
                                int cur = instk[from];
                                if (dp[cur] != ck) {
                                    continue ot;
                                }
                                from--;
                            }
                            println(-1);
                            continue mb;
                        }
                    }
                } else {
                    c = ~c;
                    vis[c] = 2;
                    qt--;
                }
            }

            long res[][] = new long[n][k+2];
            int vis1[][] = new int[n][k+2];
            res[0][0] = 1;
            long s = 0;
            for(int i=0;i<=k;++i){
                err = 0;
                s += dfs(n-1,i,res, dp,k,p,vis1);
                if(err==1){
                    println(-1);
                    continue mb;
                }
                s%= p;
            }
            err = 0;
            dfs(n-1,k+1,res, dp,k,p,vis1);
            if(err==1){
                println(-1);
                continue mb;
            }
            println(s);






        }





















    }









//    int []h,to,ne,wt;

    long t1[];
    //    long t2[];
    void update(long[] t,int i,long v){
        for(;i<t.length;i+=(i&-i)){
            t[i] += v;
        }
    }
    long get(long[] t,int i){
        long s = 0;
        for(;i>0;i-=(i&-i)){
            s += t[i];
        }
        return s;
    }

    int equal_bigger(long t[],long v){
        int s=0,p=0;
        for(int i=Integer.numberOfTrailingZeros(Integer.highestOneBit(t.length));i>=0;--i) {
            if(p+(1<<i)< t.length && s + t[p+(1<<i)] < v){
                v -= t[p+(1<<i)];
                p |= 1<<i;
            }
        }
        return p+1;
    }


    long gcd(long a,long b){ return b==0?a: gcd(b,a%b);}
    InputStream is;PrintWriter out;
    void run() throws Exception {is = System.in;
      //  is = new FileInputStream("C:\\Users\\Luqi\\Downloads\\P1600_2.in");

        out = new PrintWriter(System.out);solve();out.flush();}
    private byte[] inbuf = new byte[2];
    public int lenbuf = 0, ptrbuf = 0;
    private int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {lenbuf = is.read(inbuf);} catch (IOException e) {throw new InputMismatchException();}
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];}
    private boolean isSpaceChar(int c) {return !(c >= 33 && c <= 126);}
    private int skip() {int b;while((b = readByte()) != -1 && isSpaceChar(b));return b;}
    private double nd() {return Double.parseDouble(ns());}
    private char nc() {return (char) skip();}
    private char ncc() {int b;while((b = readByte()) != -1 && !(b >= 32 && b <= 126));return (char)b;}
    private String ns() {int b = skip();StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);b = readByte(); }
        return sb.toString();}
    private char[] ns(int n) {char[] buf = new char[n];int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) { buf[p++] = (char) b;b = readByte(); }
        return n == p ? buf : Arrays.copyOf(buf, p);}
    private String nline() {int b = skip();StringBuilder sb = new StringBuilder();
        while (!isSpaceChar(b) || b == ' ') { sb.appendCodePoint(b);b = readByte(); }
        return sb.toString();}
    private char[][] nm(int n, int m) {char[][] a = new char[n][];for (int i = 0; i < n; i++) a[i] = ns(m);return a;}
    private int[] na(int n) {int[] a = new int[n];for (int i = 0; i < n; i++) a[i] = ni();return a;}
    private long[] nal(int n) { long[] a = new long[n];for (int i = 0; i < n; i++) a[i] = nl();return a;}
    private int ni() { int num = 0, b; boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')){};
        if (b == '-') { minus = true; b = readByte(); }
        while (true) {
            if (b >= '0' && b <= '9') num = (num << 3) + (num << 1) + (b - '0');
            else return minus ? -num : num;
            b = readByte();}}
    private long nl() { long num = 0; int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')){};
        if (b == '-') { minus = true; b = readByte(); }
        while (true) {
            if (b >= '0' && b <= '9')  num = num * 10 + (b - '0');
            else return minus ? -num : num;
            b = readByte();}}
    void print(Object obj){out.print(obj);}
    void println(Object obj){out.println(obj);}
    void println(){out.println();}
}