#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9;
const int MAXN = 2e5 + 3e2;
vector<int> g[MAXN];
vector<int> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
int DistanceSum(int N, int *X, int *Y) {
if (N <= 2000) {
map<pair<int, int>, int> mp;
for (int i = 0; i < N; i++) {
mp[{X[i], Y[i]}] = i;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < 4; j++) {
if (mp.find({X[i] + dx[j], Y[i] + dy[j]}) != mp.end()) {
g[i].push_back(mp[{X[i] + dx[j], Y[i] + dy[j]}]);
}
}
}
ll ans = 0;
for (int i = 0; i < N; i++) {
queue<int> q;
q.push(i);
vector<int> d(N, 1e9);
d[i] = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
ans += d[x];
for (int y : g[x]) {
if (d[y] == 1e9) {
d[y] = d[x] + 1;
q.push(y);
}
}
}
}
ans >>= 1;
return ans % MOD;
}
sort(X, X + N);
sort(Y, Y + N);
ll ans = 0;
ll lf = 0, rg = accumulate(X, X + N, 0ll);
for (int i = 0; i < N; i++){
rg -= X[i];
ans += 1ll * i * X[i] - lf;
ans += rg - 1ll * (N - i - 1) * X[i];
lf += X[i];
}
lf = 0, rg = accumulate(Y, Y + N, 0ll);
for (int i = 0; i < N; i++){
rg -= Y[i];
ans += 1ll * i * Y[i] - lf;
ans += rg - 1ll * (N - i - 1) * Y[i];
lf += Y[i];
}
ans >>= 1;
return ans % MOD;
}
/*
7
3 3
4 3
4 4
4 5
4 6
5 3
5 4
*/
