#CW10. 差值求和(sum)

差值求和(sum)

题目描述

现在有一个长度为 nn 的正整数序列 aia_i 和一个长度为 mm 的正整数序列 bib_i。

需要求:

∑i=1n∑j=1m∣ai−bj∣\sum_{i=1}^{n}\sum_{j=1}^{m} |a_i-b_j|

因为这个值可能比较大,所以你只需要输出结果对 998244353998244353 取模后的值。

输入格式

第一行包含两个整数 nn 和 mm。

第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n。

第三行包含 mm 个整数 b1,b2,…,bmb_1, b_2, \ldots, b_m。

输出格式

输出一行一个整数,表示结果对 998244353998244353 取模后的值。

样例 1 输入

4 2
1 6 9 2
3 1

样例 1 输出

26

数据范围

对于所有测试数据,保证:

  • 1≤n,m≤3×1051 \le n, m \le 3 \times 10^5;
  • 1≤ai,bj<9982443531 \le a_i, b_j < 998244353。
测试点 n,m≤n, m \le 特殊性质
1∼61 \sim 6 10001000 无
7∼97 \sim 9 2000020000
10∼1110 \sim 11 3×1053 \times 10^5 ∀i≤n,j≤m\forall i \le n, j \le m,有 ai>bja_i > b_j
12∼1412 \sim 14 ai,bj≤1000a_i, b_j \le 1000
15∼2015 \sim 20 无