//#include"grader.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100050;
const ll MOD=1000000000;
const bool DEBUG=0;
int n,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
ll ans;
pair<int,int> coord[N];
map<pair<int,int>,int> hv,vis;
queue<pair<pair<int,int>,int>> bfs;
int DistanceSum(int _N, int *x, int *y) {
n=_N;
for (int i=0;i<n;i++) coord[i]={x[i],y[i]};
sort(coord,coord+n);
for (int i=0;i<n;i++){
hv[coord[i]]=i+1;
}
for (int i=0;i<n;i++){
vis.clear();
while (bfs.size()) bfs.pop();
bfs.push({coord[i],0});
vis[coord[i]]=1;
while (bfs.size()){
auto curr=bfs.front().first;
int cdist=bfs.front().second;
bfs.pop();
for (int i=0;i<4;i++){
if (!hv[{curr.first+dx[i],curr.second+dy[i]}]) continue;
if (vis[{curr.first+dx[i],curr.second+dy[i]}]) continue;
ans+=cdist+1;
ans%=MOD;
vis[{curr.first+dx[i],curr.second+dy[i]}]=1;
bfs.push({{curr.first+dx[i],curr.second+dy[i]},cdist+1});
}
}
}
return ans/2;
}
/*
6
1 1
2 1
2 3
3 1
3 2
3 3
*/
