#include<algorithm>
#include<vector>
using namespace std;
static const int MOD=1e9;
static const int MAXN=1e5+7;
static vector<int> connX[MAXN];
static vector<int> connY[MAXN];
static pair<pair<int,int>,int> Xsort[MAXN];
static pair<pair<int,int>,int> Ysort[MAXN];
static int Xgraph[MAXN];
static int Ygraph[MAXN];
static int Xweight[MAXN];
static int Yweight[MAXN];
static int Xtp=0;
static int Ytp=0;
static long long ans=0;
#include<cstdio>
static int N;
int dfsX(int a,int pa)
{
int subtreesize=Xweight[a];
for(int i=0;i<connX[a].size();i++)
{
if(connX[a][i]==pa) continue;
int st=dfsX(connX[a][i],a);
subtreesize+=st;
ans+=1LL*st*(N-st);
}
return subtreesize;
}
int dfsY(int a,int pa)
{
int subtreesize=Yweight[a];
for(int i=0;i<connY[a].size();i++)
{
if(connY[a][i]==pa) continue;
int st=dfsY(connY[a][i],a);
subtreesize+=st;
ans+=1LL*st*(N-st);
}
return subtreesize;
}
int DistanceSum(int N, int *X, int *Y) {
::N=N;
for(int i=0;i<N;i++) Xsort[i]=make_pair(make_pair(X[i],Y[i]),i);
for(int i=0;i<N;i++) Ysort[i]=make_pair(make_pair(Y[i],X[i]),i);
sort(Xsort,Xsort+N);
sort(Ysort,Ysort+N);
for(int i=0;i<N;i++)
{
if(
i!=0 &&
Xsort[i-1].first.first==Xsort[i].first.first &&
Xsort[i-1].first.second+1 == Xsort[i].first.second )
Xtp--;
Xweight[Xtp]++;
Xgraph[Xsort[i].second]=Xtp++;
}
for(int i=0;i<N;i++)
{
if(
i!=0 &&
Ysort[i-1].first.first==Ysort[i].first.first &&
Ysort[i-1].first.second+1 == Ysort[i].first.second )
Ytp--;
Yweight[Ytp]++;
Ygraph[Ysort[i].second]=Ytp++;
}
for(int i=0;i<N-1;i++)
{
int A=Ygraph[Xsort[i].second], B=Ygraph[Xsort[i+1].second];
int C=Xgraph[Ysort[i].second], D=Xgraph[Ysort[i+1].second];
if(Xsort[i].first.first==Xsort[i+1].first.first && Xsort[i].first.second+1==Xsort[i+1].first.second)
{
connY[A].push_back(B);
connY[B].push_back(A);
}
if(Ysort[i].first.first==Ysort[i+1].first.first && Ysort[i].first.second+1==Ysort[i+1].first.second)
{
connX[C].push_back(D);
connX[D].push_back(C);
}
}
for(int i=0;i<Xtp;i++)
{
sort(connX[i].begin(),connX[i].end());
connX[i].resize(unique(connX[i].begin(),connX[i].end())-connX[i].begin());
}
for(int i=0;i<Ytp;i++)
{
sort(connY[i].begin(),connY[i].end());
connY[i].resize(unique(connY[i].begin(),connY[i].end())-connY[i].begin());
}
dfsX(0,-1);
dfsY(0,-1);
return ans%MOD;
}
