#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
const int maxn = 1<<18;
int cx[maxn], cy[maxn];
int DistanceSum(int n, int *X, int *Y) {
ll sum = 0;
int minx = 1<<30, miny = 1<<30;
for(int i = 0; i < n; i++) {
minx = min(minx, X[i]),
miny = min(miny, Y[i]);
}
for(int i = 0; i < n; i++) {
X[i] -= minx, Y[i] -= miny;
cx[X[i]]++, cy[Y[i]]++;
}
for(int i = 1; i < n; i++) cx[i] += cx[i-1];
for(int i = 1; i < n; i++) cy[i] += cy[i-1];
for(int i = 0; i < n; i++) {
if(i) sum += (cx[X[i]-1])*1ll*X[i];
sum -= (n-cx[X[i]])*1ll*X[i];
if(i) sum += (cy[Y[i]-1])*1ll*Y[i];
sum -= (n-cy[Y[i]])*1ll*Y[i];
}
return sum%1000000000;
}
