#include<vector>
#include<algorithm>
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const ll inf=1e18;
const ll mod=1e9;
vector<int>adj[100010];
ll ans;
int sz[100010];
int s2[100010];
ll dp[100010];
void dfs(int x,int p)
{
sz[x]=s2[x];
for(int t:adj[x])
{
if(t==p)
continue;
dfs(t,x);
sz[x]+=sz[t];
}
dp[x]=sz[x];
for(int t:adj[x])
if(t!=p)
ans=(ans+dp[t]*(sz[x]-sz[t]))%mod,dp[x]+=dp[t];
return;
}
inline void solv(vector<pl>&p)
{
int n=p.size();
int i;
int cnt=0;
vector<int>ind;
ind.eb(cnt);
sort(all(p));
for(i=1;i<n;i++)
{
if(p[i].fi==p[i-1].fi&&p[i].se==p[i-1].se+1)
ind.eb(cnt);
else
ind.eb(++cnt);
}
cnt++;
for(i=0;i<cnt;i++)
s2[i]=0;
for(i=0;i<cnt;i++)
adj[i].clear();
for(i=0;i<n;i++)
s2[ind[i]]++;
vector<pair<pl,int> >P;
for(i=0;i<n;i++)
P.eb(pl(p[i].se,p[i].fi),ind[i]);
sort(all(P));
for(i=1;i<n;i++)
{
pl&t=P[i].fi;
pl&s=P[i-1].fi;
if(t.fi==s.fi&&t.se==s.se+1)
{
adj[P[i].se].eb(P[i-1].se);
adj[P[i-1].se].eb(P[i].se);
}
}
for(i=0;i<=cnt;i++)
{
sort(all(adj[i]));
adj[i].erase(unique(all(adj[i])),adj[i].end());
}
dfs(0,-1);
return;
}
int DistanceSum(int N,int*X,int*Y)
{
vector<pl>P;
int i;
for(i=0;i<N;i++)
P.eb(X[i],Y[i]);
solv(P);
P.clear();
for(i=0;i<N;i++)
P.eb(Y[i],X[i]);
solv(P);
return ans;
}
