#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define xx fi.fi
#define yy fi.se
const ll mod=1e9;//diu wtf
const int N=2e5+1,M=2e5+1;
void add(ll& x,ll y){
x+=y;
if(x<0) x+=mod;
if(x>=mod) x-=mod;
}
int n,m;
pair<pii,int>a[N];
pair<pii,int>b[N];
int l[M],r[M];//node range
int nd[N];
int par[M];
int find(int x){
if(par[x]!=x) par[x]=find(par[x]);
return par[x];
}
vector<int>adj[M];
int sz[M];
void join(int x,int y){
if(find(x)==find(y)) return;
par[find(x)]=find(y);
adj[x].push_back(y);
adj[y].push_back(x);
}
ll ans=0;
ll val[N];
void dfs(int id,int p){
sz[id]=r[id]-l[id]+1;
//cout << id << ' ' << p << endl;
for(auto cur:adj[id]){
if(cur==p) continue;
dfs(cur,id);
sz[id]+=sz[cur];
}
}
void dfs2(int id,int p){
for(auto cur:adj[id]){
if(cur==p) continue;
dfs2(cur,id);
int cl=l[cur];
while(a[cl].yy<a[l[id]].yy){
add(ans,val[cl]*(n-sz[cur])%mod);
val[cl+1]+=val[cl];
val[cl]=0;
cl++;
}
int cr=r[cur];
while(a[cr].yy>a[r[id]].yy){
add(ans,val[cr]*(n-sz[cur])%mod);
add(val[cr-1],val[cr]);
val[cr]=0;
cr--;
}
ll duh=0;
int jj=a[cl].yy-a[l[id]].yy+l[id];
for(int i=cl; i<=cr ;i++){
add(ans,-duh*(sz[cur]-duh)%mod);
duh+=val[i];
val[jj]+=val[i];
jj++;
}
add(ans,1LL*sz[cur]*(n-sz[cur])%mod);//advance
}
for(int i=l[id]; i<=r[id] ;i++) val[i]++;
ll duh=0;
for(int i=l[id]; i<=r[id] ;i++){
add(ans,duh*(sz[id]-duh)%mod);
add(duh,val[i]);
}
}
int DistanceSum(int N, int *X, int *Y){
n=N;
for(int i=1 ;i<=n ;i++) a[i]={{X[i-1],Y[i-1]},i};
sort(a+1,a+n+1);
for(int i=1; i<=n ;i++){
a[i].se=i;b[i]=a[i];
swap(b[i].fi.se,b[i].fi.fi);
if(i!=1 && a[i].fi.fi==a[i-1].fi.fi && a[i].fi.se==a[i-1].fi.se+1) r[m]=i;
else{
m++;l[m]=r[m]=i;
}
nd[i]=m;
}
sort(b+1,b+n+1);
for(int i=1; i<=m ;i++) par[i]=i;
for(int i=1; i<=n ;i++){
if(i!=1 && b[i].fi.fi==b[i-1].fi.fi && b[i].fi.se==b[i-1].fi.se+1) join(nd[b[i].se],nd[b[i-1].se]);
}
dfs(1,0);
dfs2(1,0);
return ans;
}
