#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll ;
#define sz(x) (ll)(x.size())
const ll MOD = (ll)(1e9),MX=(int)(1e5+5);
typedef pair<ll,ll> ii;
ll par[MX],parXY[MX];
ll ans,cnt[MX];
vector<pair<ll,ii> > vec[MX];
bitset<MX> vis;
vector<ii> vecD[2];
ii solve(ll node,ll p){
ii h={0,cnt[node]};
for(auto &it:vec[node])
if(it.fi!=p){
if(it.se.fi==-1)
it.se=solve(it.fi,node);
h.fi+=it.se.fi+it.se.se;
h.se+=it.se.se;
}
return h;
}
ll findSet(ll i){
if(par[i]==i)return i;
return par[i]=findSet(par[i]);
}
ll findSetXY(ll i){
if(parXY[i]==i)return i;
return parXY[i]=findSet(parXY[i]);
}
void Union(ll a,ll b){
ll x=findSet(a),y=findSet(b);
if(x<y)swap(x,y);
if(x!=y)par[x]=y,cnt[y]+=cnt[x];
}
bool UnionXY(ll a,ll b){
ll x=findSetXY(a),y=findSetXY(b);
if(x!=y){parXY[x]=y;return 1;}
return 0;
}
void work(ll idx){
vis=0;
for (ll i = 0; i < sz(vecD[idx]); ++i)
par[i]=i,parXY[i]=i,cnt[i]=1,vec[i].clear();
for (ll i = 0; i < sz(vecD[idx]);)
{
ll j=i;
while(j<sz(vecD[idx]) && vecD[idx][j].fi==vecD[idx][i].fi && (vecD[idx][i].se+(j-i))==vecD[idx][j].se){
Union(i,j);
ll k=lower_bound(vecD[idx].begin(),vecD[idx].end(),make_pair(vecD[idx][j].fi-1,vecD[idx][j].se))-vecD[idx].begin();
if(k!=sz(vecD[idx]) && vecD[idx][k]==make_pair(vecD[idx][j].fi-1,vecD[idx][j].se)){
ll a=findSet(j),b=findSet(k);
if(UnionXY(a,b)){vec[a].push_back({b,{-1,-1}}),vec[b].push_back({a,{-1,-1}});}
}
j++;
}
i=j;
}
for (ll i = 0; i < sz(vecD[idx]); ++i){
ll l=findSet(i);
if(!vis[l])vis[l]=1,ans+=solve(l,l).fi*cnt[l];
}
}
int DistanceSum(int N, int *X, int *Y) {
vecD[0].resize(N),vecD[1].resize(N);
for (ll i = 0; i < N; ++i)
vecD[0][i]={X[i],Y[i]},vecD[1][i]={Y[i],X[i]};
for (ll i = 0; i < 2; ++i)
sort(vecD[i].begin(),vecD[i].end());
work(0),work(1);
return (int)((ans/2LL)%MOD);
}
