#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000000
long long res = 0;
set<pair<int, int> > loc[2];
int t[2];
int sz[2][100005];
int re[2];
vector<int> adj[2][100005];
int st;
int n;
int dfs(int x, int y){
int id = ++re[st];
int q = y++;
set<pair<int, int> >::iterator it;
while((it = loc[st].find({x, ++q})) != loc[st].end())
loc[st].erase(it), sz[st][id]++;
while((it = loc[st].find({x, --y})) != loc[st].end())
loc[st].erase(it), sz[st][id]++;
for(y++; y < q; y++){
if(loc[st].count({x + 1, y})){
int w = dfs(x + 1, y);
adj[st][id].push_back(w);
sz[st][id] += sz[st][w];
}
if(loc[st].count({x - 1, y})){
int w = dfs(x - 1, y);
sz[st][id] += sz[st][w];
adj[st][id].push_back(dfs(x - 1, y));
}
}
res += 1LL * (n - sz[st][id]) * sz[st][id];
return id;
}
void solve(){
dfs(t[st], t[st ^ 1]);
st ^= 1;
}
int DistanceSum(int N, int *X, int *Y) {
n = N;
for(int i = 0; i < N; i++){
X[i] -= 26543;
Y[i] -= 51844;
loc[0].insert({X[i], Y[i]});
loc[1].insert({Y[i], X[i]});
}
t[0] = X[0];
t[1] = Y[0];
solve();
solve();
return res % MOD;
}
