#include <bits/stdc++.h>
typedef long long ll;
const ll maxvalue=3000000000;
const ll MOD=1000000000;
using namespace std;
ll timer,n,x[100005],y[100005],weight[100005],sz[100005],ansx,ansy;
vector<ll>adj[100005];
unordered_map<ll,bool>um,vis;
void dfs(ll x,ll y,ll from){
timer++;
if(from!=-1){
adj[timer].push_back(from);
adj[from].push_back(timer);
}
ll Y1=y,Y2=y;
while(um[x*maxvalue+Y1-1]==1){
Y1--;
}
while(um[x*maxvalue+Y2+1]==1){
Y2++;
}
for(ll i=Y1;i<=Y2;i++){
vis[x*maxvalue+i]=1;
weight[timer]++;
}
ll to=timer;
for(ll i=Y1;i<=Y2;i++){
if(vis[(x-1)*maxvalue+i]==0 && um[(x-1)*maxvalue+i]==1){
dfs(x-1,i,to);
}
if(vis[(x+1)*maxvalue+i]==0 && um[(x+1)*maxvalue+i]==1){
dfs(x+1,i,to);
}
}
}
void dfs1(ll x,ll y,ll from){
timer++;
if(from!=-1){
adj[timer].push_back(from);
adj[from].push_back(timer);
}
ll X1=x,X2=x;
while(um[(X1-1)*maxvalue+y]==1){
X1--;
}
while(um[(X2+1)*maxvalue+y]==1){
X2++;
}
for(ll i=X1;i<=X2;i++){
vis[i*maxvalue+y]=1;
weight[timer]++;
}
ll to=timer;
for(ll i=X1;i<=X2;i++){
if(vis[(i*maxvalue)+y-1]==0 && um[i*maxvalue+y-1]==1){
dfs1(i,y-1,to);
}
if(vis[i*maxvalue+y+1]==0 && um[i*maxvalue+y+1]==1){
dfs1(i,y+1,to);
}
}
}
void solve(ll node,bool f,ll par=-1){
// cout << node << ' ' << weight[node] << '\n';
sz[node]=weight[node];
for(ll to:adj[node]){
if(to==par) continue;
solve(to,f,node);
sz[node]+=sz[to];
if(f==0){
ansx+=(sz[to]*(n-sz[to]));
ansx%=MOD;
}
else{
ansy+=(sz[to]*(n-sz[to]));
ansy%=MOD;
}
}
}
int DistanceSum(int N, int *X, int *Y) {
n=(ll)N;
for(ll i=0;i<n;i++){
x[i]=(ll)X[i];
y[i]=(ll)Y[i];
}
for(ll i=0;i<n;i++) um[x[i]*maxvalue+y[i]]=1;
for(ll i=0;i<n;i++){
if(vis[x[i]*maxvalue+y[i]]==0){
dfs(x[i],y[i],-1);
}
}
solve(1,0);
for(ll i=0;i<n;i++) vis[x[i]*maxvalue+y[i]]=0;
for(ll i=1;i<=timer;i++){
weight[i]=0;
sz[i]=0;
adj[i].clear();
}
timer=0;
for(ll i=0;i<n;i++){
if(vis[x[i]*maxvalue+y[i]]==0){
dfs1(x[i],y[i],-1);
}
}
solve(1,1);
return (ansx+ansy)%MOD;
}
