#include<bits/stdc++.h>
using namespace std;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
const int MAXN=1e5+5;
const long long mod=1e9;
vector< pair<int,int> > vqx,vqy,vi[MAXN*4];
vector<int> ds[MAXN];
map< int,vector<int> > mpx,mpy;
map< pair<int,int>,int > mp;
int dsu[MAXN],cnt[MAXN];
long long dp[MAXN],F[MAXN],ans=0;
stack< pair<int,int> > st;
bool ck[MAXN];
vector< pair<int,int> > P;
pair<int,int> G[MAXN];
queue<int> Q;
int root(int i)
{
if(!dsu[i]) return i;
return root(dsu[i]);
}
void merge(int i,int j)
{
if((i=root(i))==(j=root(j)))
{
st.push({-1,-1});
return ;
}
if(cnt[i]<cnt[j]) swap(i,j);
dsu[j]=i,cnt[i]+=cnt[j],st.push({i,j});
}
void rollback()
{
int i=st.top().first,j=st.top().second;
st.pop();
if(i<0) return ;
cnt[i]-=cnt[j],dsu[j]=0;
}
void dfs(int x,int y)
{
int pre=mp[{x,y}];
ck[pre]=true;
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i],res=mp[{a,b}];
if(res&&!ck[res])
{
if(i<2) vqx.push_back({pre,res});
else vqy.push_back({pre,res});
ds[pre].push_back(res);
dfs(a,b);
}
}
}
void update(int l,int r,int u,int v,pair<int,int> val,int pos)
{
if(v<l||r<u) return ;
if(u<=l&&r<=v)
{
vi[pos].push_back(val);
return ;
}
int mid=(l+r)/2;
update(l,mid,u,v,val,pos*2);
update(mid+1,r,u,v,val,pos*2+1);
}
void solve(int l,int r,int pos)
{
for(auto v:vi[pos]) merge(v.first,v.second);
if(l==r) G[l]={cnt[root(P[l].first)],cnt[root(P[l].second)]};
else
{
int mid=(l+r)/2;
solve(l,mid,pos*2);
solve(mid+1,r,pos*2+1);
}
for(auto v:vi[pos]) rollback();
vi[pos].clear();
}
void dfs2(int i)
{
ans+=F[i];
for(auto v:ds[i])
{
F[v]+=F[i];
dfs2(v);
}
}
int DistanceSum(int N,int *X,int *Y)
{
for(int i=1;i<=N;i++) cnt[i]=1;
for(int i=0;i<N;i++) mpx[X[i]].push_back(Y[i]),mpy[Y[i]].push_back(X[i]),mp[{X[i],Y[i]}]=i+1;
for(auto& v:mpx) sort(v.second.begin(),v.second.end());
for(auto& v:mpy) sort(v.second.begin(),v.second.end());
for(int i=1;i<=N;i++) dp[i]=mod;
dp[1]=0,Q.push(1);
while(!Q.empty())
{
int a=Q.front();
Q.pop();
for(int i=0;i<4;i++)
{
int res=mp[{X[a-1]+dx[i],Y[a-1]+dy[i]}];
if(res&&dp[res]==mod) dp[res]=dp[a]+1,Q.push(res);
}
}
for(int i=1;i<=N;i++) F[1]+=dp[i];
dfs(X[0],Y[0]);
int m=0;
if(vqx.size())
{
for(auto v:mpx)
{
int pre=-1;
for(auto u:v.second)
{
if(pre+1==u) merge(mp[{v.first,pre}],mp[{v.first,u}]);
pre=u;
}
}
for(auto v:vqx)
{
pair<int,int> res={root(v.first),root(v.second)};
if(res.first>res.second) swap(res.first,res.second);
P.push_back(res);
}
sort(P.begin(),P.end());
P.erase(unique(P.begin(),P.end()),P.end());
m=P.size();
for(int i=0;i<m;i++)
{
update(0,m-1,0,i-1,P[i],1);
update(0,m-1,i+1,m-1,P[i],1);
}
solve(0,m-1,1);
for(auto v:vqx)
{
int he=1;
pair<int,int> res={root(v.first),root(v.second)};
if(res.first>res.second) swap(res.first,res.second),he=-1;
int pos=lower_bound(P.begin(),P.end(),res)-P.begin();
F[v.second]=(G[pos].first-G[pos].second)*he;
}
while(!st.empty()) rollback();
P.clear();
}
if(vqy.size())
{
for(auto v:mpy)
{
int pre=-1;
for(auto u:v.second)
{
if(pre+1==u) merge(mp[{pre,v.first}],mp[{u,v.first}]);
pre=u;
}
}
for(auto v:vqy)
{
pair<int,int> res={root(v.first),root(v.second)};
if(res.first>res.second) swap(res.first,res.second);
P.push_back(res);
}
sort(P.begin(),P.end());
P.erase(unique(P.begin(),P.end()),P.end());
m=P.size();
for(int i=0;i<m;i++)
{
update(0,m-1,0,i-1,P[i],1);
update(0,m-1,i+1,m-1,P[i],1);
}
solve(0,m-1,1);
for(auto v:vqy)
{
int he=1;
pair<int,int> res={root(v.first),root(v.second)};
if(res.first>res.second) swap(res.first,res.second),he=-1;
int pos=lower_bound(P.begin(),P.end(),res)-P.begin();
F[v.second]=(G[pos].first-G[pos].second)*he;
}
while(!st.empty()) rollback();
P.clear();
}
dfs2(1);
return (ans/2)%mod;
}
