#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = x; i < y; ++i)
#define pb push_back
#define x first
#define y second
long long M;
long long ans;
set<pair<int, int>> g;
vector<pair<int ,int>> D;
map<pair<int, int>, int> ind;
void Add(int x){
ans = (ans + (long long)x)%M;
}
void bfs(pair<int, int> start){
set<pair<int, int>> vis;
queue<pair<pair<int, int>, int>> q;
q.push({start, 0});
while(!q.empty()){
auto cur = q.front();
q.pop();
if (vis.count(cur.x) == 0){
vis.insert(cur.x);
if (ind[cur.x] > ind[start]){
Add(cur.y);
}
pair<int, int> nex;
FOR(i, 0, 4){
nex = make_pair(cur.x.x + D[i].x, cur.x.y + D[i].y);
if (g.count(nex) != 0 && vis.count(nex) == 0){
q.push({nex, cur.y + 1});
}
}
}
}
}
int DistanceSum(int N, int *X, int *Y) {
M = 1e9;
ans = 0;
D = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
FOR(i, 0, N){
g.insert({X[i], Y[i]});
ind[make_pair(X[i], Y[i])] = i;
}
for(auto i: g){
bfs(i);
}
return ans;
}
