#include<map>
#include<string.h>
#include<algorithm>
using namespace std;
map<int,int>ch;
int w,N,pos[100010],p,k,cnt,s,e,sw,val,st[100010],top,dp[100010],len[100010],n,check[100010];
long long dap;
struct data{
int x,y;
bool operator<(const data&r)const{
if(x==r.x) return y<r.y;
return x<r.x;
}
}a[100010];
struct data2{
int x,y;
bool operator<(const data2&r)const{
if(x==r.x) return y<r.y;
return x<r.x;
}
}con[100010];
void uw(int i)
{
int j;
cnt++; sw=0;
for(j=k;j<=i;j++){
if(s==0 && e==0) break;
if(ch[a[j].y]>=s && sw==0){w++; con[w].x=cnt; con[w].y=ch[a[j].y]; sw=1;}
if(ch[a[j].y]<s) sw=0;
}
len[cnt]=i-k+1;
k=i+1;
}
void dfs(int x)
{
int i;
check[x]=1;
for(i=pos[x];;i++)
{
if(x!=con[i].x) break;
if(check[con[i].y]==1) continue;
dfs(con[i].y);
dp[x]+=dp[con[i].y];
}
dp[x]+=len[x];
dap+=(long long)dp[x]*(long long)(n-dp[x]);
dap%=1000000000;
}
int DistanceSum(int N, int *X, int *Y)
{
n=N;
int i,j;
for(i=0;i<N;i++) a[i].x=X[i], a[i].y=Y[i];
sort(a,a+N);
for(i=0;i<N;i++)
{
if(a[i].x==a[i+1].x && a[i+1].y!=a[i].y+1) st[++top]=i;
if(a[i].x!=a[i+1].x)
{
st[++top]=i;
for(j=1;j<=top;j++) uw(st[j]);
s=e+1; e=cnt; val=s; top=0;
for(j=p;j<=i;j++){
ch[a[j].y]=val;
if(a[j+1].y!=a[j].y+1) val++;
}
p=i+1;
}
}
for(i=w+1;i<=w*2;i++)
{
con[i].x=con[i-w].y; con[i].y=con[i-w].x;
}
w*=2;
sort(con+1,con+w+1);
for(i=1;i<=w;i++){
if(con[i].x!=con[i-1].x) pos[con[i].x]=i;
}
dfs(1);
for(i=0;i<N;i++) a[i].y=X[i], a[i].x=Y[i];
sort(a,a+N);
top=0; memset(len,0,sizeof len); memset(dp,0,sizeof dp); memset(con,0,sizeof con); w=0; p=0; cnt=0; s=0; e=0;
memset(check,0,sizeof check); ch.clear();
for(i=0;i<N;i++)
{
if(a[i].x==a[i+1].x && a[i+1].y!=a[i].y+1) st[++top]=i;
if(a[i].x!=a[i+1].x)
{
st[++top]=i;
for(j=1;j<=top;j++) uw(st[j]);
s=e+1; e=cnt; val=s; top=0;
for(j=p;j<=i;j++){
ch[a[j].y]=val;
if(a[j+1].y!=a[j].y+1) val++;
}
p=i+1;
}
}
for(i=w+1;i<=w*2;i++)
{
con[i].x=con[i-w].y; con[i].y=con[i-w].x;
}
w*=2;
sort(con+1,con+w+1);
for(i=1;i<=w;i++){
if(con[i].x!=con[i-1].x) pos[con[i].x]=i;
}
dfs(1);
return dap;
}
