#include <iostream>
#include <cstdio>
#include <unordered_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}};
unordered_map <long long, int> Points;
info File[MAX_POINTS];
int deb = 0, fin = 0;
long long Hash(int lig, int col) {
return ((long long)lig << 32) + (long long)col;
}
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[Hash(nvLig, nvCol)] -- > 0)
File[fin ++] = {nvLig, nvCol, cur.dist + 1};
}
return;
}
long long Bfs(info dep) {
Points[Hash(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[Hash(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[Hash(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;
}
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;
}
