#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100050;
const ll MOD=1000000000;
const bool DEBUG=0;
int n,cx,cnt[N],grpcnt,ingrp[N];
ll ans,dist[N];
vector<pair<int,int>> curr,grps[N];
pair<int,int> coord[N];
map<int,vector<pair<int,int>>> mp;
map<pair<int,int>,int> hv;
ll f(ll num){
return (1+num)*num/2%MOD;
}
void dfs(int nde,int par,pair<int,int> connection,bool up){
vector<array<ll,2>> frntsum,frntcnt,bcksum,bckcnt;
int cx=coord[grps[nde][0].second-1].first,cy=INT_MAX,cz=grps[nde].size();
ll csum=0,ccnt=0,lzsum=0,lzcnt=0,dup=0;
frntsum.resize(cz); frntcnt.resize(cz); bcksum.resize(cz); bckcnt.resize(cz);
if (DEBUG) cerr<<"dfs"<<cx<<"::"<<connection.first<<","<<connection.second<<"\n";
for (auto i:grps[nde]){
if (!hv[{cx+1,i.first}]) continue;
if (ingrp[hv[{cx+1,i.first}]]==par) continue;
cy=min(cy,i.first);
if (hv[{cx+1,i.first+1}]&&i!=grps[nde].back()) continue;
dfs(ingrp[hv[{cx+1,i.first}]],nde,{cy,i.first},0);
cy=INT_MAX;
}
cy=INT_MAX;
for (auto i:grps[nde]){
if (!hv[{cx-1,i.first}]) continue;
if (ingrp[hv[{cx-1,i.first}]]==par) continue;
cy=min(cy,i.first);
if (hv[{cx-1,i.first+1}]&&i!=grps[nde].back()) continue;
dfs(ingrp[hv[{cx-1,i.first}]],nde,{cy,i.first},1);
cy=INT_MAX;
}
// down down, up up
if (DEBUG) cerr<<"PROCESSING"<<ans<<"\n";
for (auto i:grps[nde]){
if (DEBUG) cerr<<cx<<","<<i.first<<"\n";
csum+=ccnt;
csum%=MOD;
lzsum+=lzcnt;
lzsum%=MOD;
if (DEBUG) cerr<<csum<<","<<ccnt<<";"<<lzsum<<","<<lzcnt<<":"<<ans<<"\n";
if (hv[{cx-1,i.first}]&&ingrp[hv[{cx-1,i.first}]]!=par){
lzcnt+=cnt[hv[{cx-1,i.first}]];
lzsum+=dist[hv[{cx-1,i.first}]]+cnt[hv[{cx-1,i.first}]];
lzcnt%=MOD; lzsum%=MOD;
ans+=ccnt*(dist[hv[{cx-1,i.first}]]+cnt[hv[{cx-1,i.first}]]);
ans+=csum*cnt[hv[{cx-1,i.first}]];
ans%=MOD;
if (DEBUG) cerr<<ans<<"::\n";
}else{
csum+=lzsum;
csum%=MOD;
ccnt+=lzcnt;
ccnt%=MOD;
lzsum=lzcnt=0;
}
}
csum=lzsum=ccnt=lzcnt=0;
for (auto i:grps[nde]){
if (DEBUG) cerr<<cx<<","<<i.first<<"\n";
csum+=ccnt;
csum%=MOD;
lzsum+=lzcnt;
lzsum%=MOD;
if (DEBUG) cerr<<csum<<","<<ccnt<<";"<<lzsum<<","<<lzcnt<<":"<<ans<<"\n";
if (hv[{cx+1,i.first}]&&ingrp[hv[{cx+1,i.first}]]!=par){
lzcnt+=cnt[hv[{cx+1,i.first}]];
lzsum+=dist[hv[{cx+1,i.first}]]+cnt[hv[{cx+1,i.first}]];
lzcnt%=MOD; lzsum%=MOD;
ans+=ccnt*(dist[hv[{cx+1,i.first}]]+cnt[hv[{cx+1,i.first}]]);
ans+=csum*cnt[hv[{cx+1,i.first}]];
ans%=MOD;
if (DEBUG) cerr<<ans<<"::\n";
}else{
csum+=lzsum;
csum%=MOD;
ccnt+=lzcnt;
ccnt%=MOD;
lzsum=lzcnt=0;
}
}
// down to up
for (int i=0;i<cz;i++){
if (i){
frntsum[i][0]=(frntsum[i-1][0]+frntcnt[i-1][0])%MOD;
frntcnt[i][0]=frntcnt[i-1][0];
frntsum[i][1]=(frntsum[i-1][1]+frntcnt[i-1][1])%MOD;
frntcnt[i][1]=frntcnt[i-1][1];
}
dup+=ccnt;
ccnt+=i+1;
ccnt%=MOD; dup%=MOD;
if (hv[{cx-1,grps[nde][i].first}]&&ingrp[hv[{cx-1,grps[nde][i].first}]]!=par){
frntcnt[i][0]+=cnt[hv[{cx-1,grps[nde][i].first}]];
frntsum[i][0]+=dist[hv[{cx-1,grps[nde][i].first}]]+cnt[hv[{cx-1,grps[nde][i].first}]];
frntsum[i][0]%=MOD;
}
if (hv[{cx+1,grps[nde][i].first}]&&ingrp[hv[{cx+1,grps[nde][i].first}]]!=par){
frntcnt[i][1]+=cnt[hv[{cx+1,grps[nde][i].first}]];
frntsum[i][1]+=dist[hv[{cx+1,grps[nde][i].first}]]+cnt[hv[{cx+1,grps[nde][i].first}]];
frntsum[i][1]%=MOD;
}
}
for (int i=cz-1;~i;i--){
if (i!=cz-1){
bcksum[i][0]=(bcksum[i+1][0]+bckcnt[i+1][0])%MOD;
bckcnt[i][0]=bckcnt[i+1][0];
bcksum[i][1]=(bcksum[i+1][1]+bckcnt[i+1][1])%MOD;
bckcnt[i][1]=bckcnt[i+1][1];
}
if (hv[{cx-1,grps[nde][i].first}]&&ingrp[hv[{cx-1,grps[nde][i].first}]]!=par){
bckcnt[i][0]+=cnt[hv[{cx-1,grps[nde][i].first}]];
bcksum[i][0]+=dist[hv[{cx-1,grps[nde][i].first}]]+cnt[hv[{cx-1,grps[nde][i].first}]];
bcksum[i][0]%=MOD;
}
if (hv[{cx+1,grps[nde][i].first}]&&ingrp[hv[{cx+1,grps[nde][i].first}]]!=par){
bckcnt[i][1]+=cnt[hv[{cx+1,grps[nde][i].first}]];
bcksum[i][1]+=dist[hv[{cx+1,grps[nde][i].first}]]+cnt[hv[{cx+1,grps[nde][i].first}]];
bcksum[i][1]%=MOD;
}
}
if (DEBUG) for (int i=0;i<cz;i++) cerr<<frntsum[i][0]<<" "<<frntsum[i][1]<<" "<<frntcnt[i][0]<<" "<<frntcnt[i][1]<<"\n";
for (int i=0;i<cz;i++){
ans+=bcksum[i][0]+bcksum[i][1];
ans%=MOD;
if (i) ans+=frntsum[i-1][0]+frntsum[i-1][1]+frntcnt[i-1][0]+frntcnt[i-1][1];
ans%=MOD;
if (DEBUG) cerr<<cx<<","<<grps[nde][i].first<<":"<<ans<<"\n";
if (!hv[{cx+1,grps[nde][i].first}]||ingrp[hv[{cx+1,grps[nde][i].first}]]==par) continue;
ans+=(dist[hv[{cx+1,grps[nde][i].first}]]+cnt[hv[{cx+1,grps[nde][i].first}]])%MOD*bckcnt[i][0];
ans%=MOD;
ans+=bcksum[i][0]*cnt[hv[{cx+1,grps[nde][i].first}]];
ans%=MOD;
if (i){
ans+=(dist[hv[{cx+1,grps[nde][i].first}]]+cnt[hv[{cx+1,grps[nde][i].first}]])%MOD*frntcnt[i-1][0];
ans%=MOD;
ans+=(frntsum[i-1][0]+frntcnt[i-1][0])*cnt[hv[{cx+1,grps[nde][i].first}]];
ans%=MOD;
}
if (DEBUG) cerr<<cx<<","<<grps[nde][i].first<<":"<<ans<<"\n";
}
for (int i=0;i<cz;i++){
if (up){
cnt[hv[{cx,grps[nde][i].first}]]=cnt[hv[{cx-1,grps[nde][i].first}]]+1;
dist[hv[{cx,grps[nde][i].first}]]=dist[hv[{cx-1,grps[nde][i].first}]]+cnt[hv[{cx-1,grps[nde][i].first}]];
dist[hv[{cx,grps[nde][i].first}]]%=MOD;
}else{
cnt[hv[{cx,grps[nde][i].first}]]=cnt[hv[{cx+1,grps[nde][i].first}]]+1;
dist[hv[{cx,grps[nde][i].first}]]=dist[hv[{cx+1,grps[nde][i].first}]]+cnt[hv[{cx+1,grps[nde][i].first}]];
dist[hv[{cx,grps[nde][i].first}]]%=MOD;
}
if (grps[nde][i].first==connection.first){
if (i){
cnt[hv[{cx,grps[nde][i].first}]]+=frntcnt[i-1][0]+frntcnt[i-1][1]+i;
dist[hv[{cx,grps[nde][i].first}]]+=frntsum[i-1][0]+frntsum[i-1][1]+frntcnt[i-1][0]+frntcnt[i-1][1]+f(i);
dist[hv[{cx,grps[nde][i].first}]]%=MOD;
}
}
if (grps[nde][i].first==connection.second){
if (i<cz-1){
cnt[hv[{cx,grps[nde][i].first}]]+=bckcnt[i+1][0]+bckcnt[i+1][1]+cz-i-1;
dist[hv[{cx,grps[nde][i].first}]]+=bcksum[i+1][0]+bcksum[i+1][1]+bckcnt[i+1][0]+bckcnt[i+1][1]+f(cz-i-1);
dist[hv[{cx,grps[nde][i].first}]]%=MOD;
}
}
if (DEBUG) cerr<<cx<<":::"<<grps[nde][i].first<<":"<<cnt[hv[{cx,grps[nde][i].first}]]<<","<<dist[hv[{cx,grps[nde][i].first}]]<<"\n";
}
for (int i=0;i<cz;i++) ans+=f(i);
}
void addgrp(){
grps[++grpcnt]=curr;
for (auto i:curr) ingrp[i.second]=grpcnt;
curr.clear();
}
int DistanceSum(int _N, int *x, int *y) {
n=_N;
for (int i=0;i<n;i++) coord[i]={x[i],y[i]};
sort(coord,coord+n);
for (int i=0;i<n;i++){
hv[coord[i]]=i+1;
mp[coord[i].first].push_back({coord[i].second,i+1});
}
for (auto i:mp){
cx=i.first;
curr.clear();
for (auto j:i.second){
if (curr.empty()||j.first==curr.back().first+1){
curr.push_back(j);
}else{
addgrp();
curr.push_back(j);
}
}
if (curr.size()) addgrp();
}
dfs(1,1,{-1,-1},0);
return ans;
}
/*
6
1 1
2 1
2 3
3 1
3 2
3 3
*/
