D - Sum of Differences 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

長さ N の正整数列 A = (A_1, A_2, \dots, A_N) および長さ M の正整数列 B = (B_1, B_2, \dots, B_M) が与えられます。

\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} |A_i - B_j| の値を 998244353 で割ったあまりを求めてください。

制約

  • 1 \leq N,M \leq 3 \times 10^5
  • 1 \leq A_i, B_j < 998244353
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_M

出力

答えを 1 行に出力せよ。

入力例 1

4 2
1 6 9 2
3 1

出力例 1

26

答えは |1-3| + |1-1| + |6-3| + |6-1| + |9-3| + |9-1| + |2-3| + |2-1| = 2+0+3+5+6+8+1+1 = 26 です。

入力例 2

8 8
185991676 311812083 311812083 84357963 185991676 185991676 724020528 369175631
455049197 387671868 4361724 724020528 724020528 455049197 455049197 724020528

出力例 2

529117255

Score : 400 points

Problem Statement

You are given a length-N sequence of positive integers A = (A_1, A_2, \dots, A_N) and a length-M sequence of positive integers B = (B_1, B_2, \dots, B_M).

Find the value of \displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} |A_i - B_j|, modulo 998244353.

Constraints

  • 1 \leq N,M \leq 3 \times 10^5
  • 1 \leq A_i, B_j < 998244353
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_M

Output

Output the answer in one line.

Sample Input 1

4 2
1 6 9 2
3 1

Sample Output 1

26

The answer is |1-3| + |1-1| + |6-3| + |6-1| + |9-3| + |9-1| + |2-3| + |2-1| = 2+0+3+5+6+8+1+1 = 26.

Sample Input 2

8 8
185991676 311812083 311812083 84357963 185991676 185991676 724020528 369175631
455049197 387671868 4361724 724020528 724020528 455049197 455049197 724020528

Sample Output 2

529117255