#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
const int mod = 1e9;
typedef pair<int, int> pii;
int n;
int x[maxn], y[maxn];
int prefX[maxn], prefY[maxn];
// -------- BFS STUFF --------
int dist[maxn];
int linha[] = {-1, 1, 0, 0};
int coluna[] = {0, 0, -1, 1};
// ---------------------------
map<pii, int> ind;
void bfs(int x, int y)
{
queue<pii> fila;
dist[ind[{x, y}]] = 0, fila.push({x, y});
while (!fila.empty())
{
int x = fila.front().first, y = fila.front().second;
fila.pop();
int u = ind[{x, y}];
for (int i = 0; i < 4; i++)
{
int a = x+linha[i], b = y+coluna[i];
if (ind.find({a, b}) == ind.end() || dist[ind[{a, b}]] != -1) continue;
dist[ind[{a, b}]] = dist[u]+1, fila.push({a, b});
}
}
}
int solve_small(void)
{
int ans = 0;
for (int i = 1; i <= n; i++)
ind[{x[i], y[i]}] = i;
for (int i = 1; i <= n; i++)
{
memset(dist, -1, sizeof dist);
bfs(x[i], y[i]);
for (int j = 1; j < i; j++)
ans = (ans+dist[j])%mod;
}
return ans;
}
int DistanceSum(int N, int *X, int *Y)
{
n = N;
for (int i = 1; i <= n; i++)
x[i] = X[i-1], y[i] = Y[i-1];
if (n <= 2000) return solve_small();
sort(x+1, x+n+1); sort(y+1, y+n+1);
for (int i = 1; i <= n; i++)
{
prefX[i] = (prefX[i-1] + x[i])%mod;
prefY[i] = (prefY[i-1] + y[i])%mod;
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
long long soma = (1ll*(i-1)*x[i] - 1ll*prefX[i-1] + 1ll*mod)%mod;
ans = (ans+soma)%mod;
soma = (1ll*(i-1)*y[i] - 1ll*prefY[i-1] + 1ll*mod)%mod;
ans = (ans+soma)%mod;
}
return ans;
}
