#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
const long long MOD = (1000 * 1000 * 1000);
const int MAX_POINTS = (100 * 1000);
struct info {
int lig, col;
long long dist;
};
int Dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
map <pair <int, int>, int> Points;
info File[MAX_POINTS];
int deb = 0, fin = 0;
void Add(info cur) {
for (int i = 0; i < 4; i ++)
{
int nvLig = cur.lig + Dir[i][0], nvCol = cur.col + Dir[i][1];
if (Points[make_pair(nvLig, nvCol)] -- > 0)
File[fin ++] = {nvLig, nvCol, cur.dist + 1};
}
return;
}
long long Bfs(info dep) {
Points[make_pair(dep.lig, dep.col)] --;
deb = 0, fin = 0;
File[fin ++] = dep;
long long ans = 0;
while (deb < fin)
{
// printf("%lld ", File[deb].dist);
ans += File[deb].dist;
Add(File[deb ++]);
}
for (int i = 0; i < fin; i ++)
{
Points[make_pair(File[i].lig, File[i].col)] = 1;
}
return ans % MOD;
}
int DistanceSum(int nbPoints, int *X, int *Y) {
long long sumX = 0, sumY = 0;
for (int i = 0; i < nbPoints; i ++)
{
Points[make_pair(X[i], Y[i])] ++;
sumX += X[i], sumY += Y[i];
}
long long ans = 0;
if (nbPoints <= 2000)
{
for (int i = 0; i < nbPoints; i ++)
{
ans += Bfs({X[i], Y[i], 0LL});
// printf("%lld ", ans);
}
ans %= MOD;
return ans / 2;
}
return 0;
sort(X, X + nbPoints);
sort(Y, Y + nbPoints);
for (int i = 0; i < nbPoints; i ++)
{
ans += sumX - (nbPoints - i) * X[i];
sumX -= X[i];
ans += sumY - (nbPoints - i) * Y[i];
sumY -= Y[i];
ans %= MOD;
}
return ans;
}
