#include <bits/stdc++.h>
using namespace std;
long long res = 0;
set<pair<int, int> > loc[2];
int t[2], re[2], st, n;
long long sz[2][100005];
vector<int> adj[2][100005];
int dfs(int x, int y){
int id = ++re[st], 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++){
for(int j = -1; j <= 1; j += 2){
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];
}
}
}
res += (n - sz[st][id]) * sz[st][id];
return id;
}
int DistanceSum(int N, int *X, int *Y) {
n = N;
for(int i = 0; i < N; i++){
X[i] -= 9;
Y[i] -= 9;
loc[0].insert({X[i], Y[i]});
loc[1].insert({Y[i], X[i]});
}
t[0] = X[0];
t[1] = Y[0];
dfs(t[0], t[1]);
st ^= 1;
dfs(t[1], t[0]);
return res % 1000000000;
}
