#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 42, M = 2e3 + 10, INF = 1e10, MOD = 1e9;
vector<int> adj[N];
ll n, x[N], y[N], id[M][M], dist[M], occ[N], sumX[N], cumOcc[N];
ll dl[] = {0, 0, 1, -1},
dc[] = {1, -1, 0, 0};
void BFS(int i) {
for(int j = 0; j < n; j++)
dist[j] = INF;
dist[i] = 0;
queue<int> q;
q.push(i);
while(!q.empty()) {
int j = q.front();
q.pop();
for(int k : adj[j]) {
if(dist[k] == INF) {
dist[k] = dist[j] + 1;
q.push(k);
}
}
}
}
int getSumX() {
for(int i = 0; i < N; i++)
occ[i] = cumOcc[i] = sumX[i] = 0;
for(int i = 0; i < n; i++)
occ[x[i]]++;
cumOcc[0] = occ[0];
for(int i = 1; i < N; i++)
cumOcc[i] = (cumOcc[i-1] + occ[i]) % MOD;
for(int i = 1; i < N; i++)
sumX[i] = (sumX[i-1] + occ[i-1] * (i-1)) % MOD;
ll diffX = 0;
for(int i = 0; i < n; i++) {
diffX += (diffX + (occ[i] * ((cumOcc[i] * i - sumX[i] + MOD) % MOD))) % MOD;
}
return diffX;
}
signed DistanceSum(int n1, int *X, int *Y) {
n = n1;
ll minx = INF, miny = INF;
for(int i = 0; i < n; i++) {
x[i] = X[i];
y[i] = Y[i];
minx = min(minx, x[i]);
miny = min(miny, y[i]);
}
for(int i = 0; i < n; i++) {
x[i] -= minx;
y[i] -= miny;
}
if(n <= 2000) {
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
id[i][j] = -1;
for(int i =0; i < n; i++)
id[x[i]][y[i]] = i;
for(int i = 0; i < n; i++) {
ll l = x[i], c = y[i];
for(int j = 0; j < 4; j++) {
ll l2 = l + dl[j], c2 = c + dc[j];
if(-1 < l2 && l2 < n && -1 < c2 && c2 < n) {
if(id[l2][c2] != -1) {
adj[i].push_back(id[l2][c2]);
adj[id[l2][c2]].push_back(i);
}
}
}
}
ll sum = 0;
for(int i = 0; i < n; i++) {
BFS(i);
ll t = 0;
for(int j = 0; j < n; j++)
sum = (dist[j] + sum) % MOD;
for(int j = 0; j < n; j++)
t += dist[j];
}
return sum/2;
}
ll sum = 0;
sum = getSumX();
for(int i = 0; i < n; i++)
swap(x[i], y[i]);
sum = (sum + getSumX()) % MOD;
return sum;
}
