Observations

We may sort the elements of \(A\) in ascending order to make \(A_1 \leq A_2 \leq \dots \leq A_N\) without changing the answer, so we assume that \(A\) is sorted in ascending order.

\(|x - y|\) takes \(x-y\) if \(x \geq y\) and \(y-x\) if \(x < y\). This property suggests us to consider \(A_i \geq B_j\) cases and \(A_i < B_j\) separately.

Fix \(B_j\), denoted by \(y\). The value \(\sum_{i = 1}^{N} |A_i - y|\) can be represented as the sum of:

• the sum of \((A_i - y)\) for all \(A_i\) with \(A_i \geq y\);
• the sum of \((y - A_i)\) for all \(A_i\) with \(A_i < y\).

---

Evaluating the former

Here, let \(i_y\) be the minimum \(i\) with \(A_i \geq y\) (or \(N+1\) if there is no such \(i\)). Then the number of \(A_i\) with \(A_i \geq y\) is \((N+1-i_y)\), so the former sum can be deformed as follows:

\[\sum_{A_i \geq y} (A_i - y) = \sum_{A_i \geq y} A_i - \sum_{A_i \geq y} y = (A_{i_y+1} + \dots + A_N) - (N + 1 - i_y)y\]

Therefore, the value above can be computed fast if \(i_y\) for the given \(y\) and \((A_{i_y+1} + \dots + A_N)\) can be computed fast.

The minimum \(i\) with \(A_i \geq y\) can be found with a binary search, since \(A\) is sorted in ascending order.

The sum \((A_{i_y + 1} + \dots + A_N)\) can be precalculated for each \(i_y \in \{1, \dots, N+1\}\) in ascending order, so that we do not need to evaluate it independently for each \(y\).

By these speedups, the sought value can be evaluated fast.

Evaluating the latter

Let \(i_y\) be the minimum \(i\) with \(A_i \geq y\) (or \(N+1\) if there is no such \(i\)). Then the number of \(A_i\) with \(A_i < y\) is \(i_y-1\), so the latter sum can be deformed as follows:

\[\sum_{A_i < y} (y - A_i) = \sum_{A_i < y} y - \sum_{A_i < y} A_i = (i_y - 1)y - (A_1 + \dots + A_{i_y - 1}).\]

This can be evaluated fast in the same manner as the algorithm for the former.

---

Overall procedure

By the observations so far, the problem can be solved by implementing the following procedure:

• Sort \(A\) in ascending order.
• For \(i \in \{0, 1, \dots, N+1\}\), compute \((A_1 + \dots + A_i)\) as cumulative sums.
• For \(i \in \{0, 1, \dots, N+1\}\), compute \((A_i + \dots + A_N)\) as cumulative sums.
• Initialize the variable \(ans\) with \(0\).
• For \(j = 1, \dots, M\), let \(y = B_j\), and perform the following:
  • Perform a binary search to find the minimum \(i\) with \(A_i \geq y\), and let \(i_y\) be the value (or \(N+1\) if there is no such \(i\)).
  • Add \((A_{i_y+1} + \dots + A_N) - (N + 1 - i_y)y\) to \(ans\).
  • Add \((i_y - 1)y - (A_1 + \dots + A_{i_y - 1})y\) to \(ans\).
• Print \(ans \bmod 998244353\).

The time complexity is \(O((N+M) \log (N+M))\), where sorting and binary searching are the bottleneck. This is fast enough.

Note that you need to take modulus time to time. Especially, if you are using a fixed-size integers, note that you need to take modulus in the course of the calculation, as well as right before printing the answer, to avoid overflows.

Sample code (C++)

#include <iostream>
using std::cin;
using std::cout;
#include <vector>
using std::vector;
#include <algorithm>
using std::sort;

typedef long long int ll;

const ll MOD = 998244353;

ll n, m;
vector<ll> a, b;


void solve () {
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());

	// sum[0, i), sum[i, n)
	vector<ll> apre(n+1, 0LL), asuf(n+1, 0LL);
	apre[0] = 0;
	for (ll i = 0; i < n; i++) {
		apre[i+1] = (apre[i] + a[i]);
	}
	asuf[n] = 0;
	for (ll i = n-1; i >= 0; i--) {
		asuf[i] = (asuf[i+1] + a[i]);
	}

	ll ans = 0;
	for (ll i = 0; i < m; i++) {
		// a[<x] < b[i], a[>=x] >= b[i]
		ll ok = n, ng = -1;
		while (ng + 1 < ok) {
			ll med = (ok + ng) / 2;
			if (a[med] >= b[i]) {
				ok = med;
			} else {
				ng = med;
			}
		}
		const ll x = ok;

		// prefix sum
		ans += ((b[i] * x) - apre[x]) % MOD;
		// suffix sum
		ans += (asuf[x] - (b[i] * (n-x))) % MOD;
	}
	ans %= MOD;

	cout << ans << "\n";
	return;	
}

int main (void) {
	cin >> n >> m;
	a.resize(n);
	b.resize(m);
	for (ll i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (ll i = 0; i < m; i++) {
		cin >> b[i];
	}

	solve();

	
	return 0;
}