#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define mod 10000000000LL
#define mod2 1000000000LL
int head[maxn];
long long all, now, ans;
long long sum[maxn], val[maxn];
bool vis[maxn];
vector<int> from[maxn];
map<pair<int,int>, int> p;
void dfs(int x,int h) {
int i;
vis[x] = 1; now = (now + val[x]*h)%mod;
for(i=0;i<from[x].size();i++) {
if(!vis[from[x][i]]) {
dfs(from[x][i],h+1);
sum[x] = (sum[x] + sum[from[x][i]])%mod;
}
}
sum[x] = (sum[x] + val[x])%mod;
}
void dfs2(int x) {
int i;
vis[x] = 1;
// printf("dfs2 %d : now = %lld => %lld\n",x,now,now*val[x]);
ans = (ans + now*val[x]);
for(i=0;i<from[x].size();i++) {
if(!vis[from[x][i]]) {
now = (now + all - sum[from[x][i]] - sum[from[x][i]] + mod)%mod;
dfs2(from[x][i]);
now = (now - all + sum[from[x][i]] + sum[from[x][i]] + mod)%mod;
}
}
}
int findhead(int x) {
if(head[x]==x) return x;
return head[x] = findhead(head[x]);
}
void solve(int N, int *X, int *Y,int type) {
int i,x;
pair<int,int> t;
map<pair<int,int>, int>::iterator it;
p.clear();
memset(sum,0,sizeof(sum)); memset(val,0,sizeof(val));
for(i=0;i<N;i++) head[i] = i, from[i].clear();
for(i=0;i<N;i++) {
if(type==0) p[{X[i],Y[i]}] = i;
else p[{Y[i],X[i]}] = i;
}
for(it=p.begin();it!=p.end();++it) {
t = it->first;
if(p.find({t.first,t.second+1})!=p.end()) head[findhead(p[t])] = findhead(p[{t.first,t.second+1}]);
}
for(i=0;i<N;i++) val[findhead(i)]++;
for(it=p.begin();it!=p.end();++it) {
t = it->first;
if(p.find({t.first+1,t.second})!=p.end()) from[findhead(p[t])].push_back(findhead(p[{t.first+1,t.second}]));
if(p.find({t.first-1,t.second})!=p.end()) from[findhead(p[t])].push_back(findhead(p[{t.first-1,t.second}]));
}
for(i=0;i<N;i++) if(val[i]) x = i;
all = N; now = 0;
memset(vis,0,sizeof(vis));
dfs(x,0);
memset(vis,0,sizeof(vis));
dfs2(x);
// printf("ans = %lld\n",ans);
}
int DistanceSum(int N,int* X,int* Y) {
ans = 0;
solve(N,X,Y,0);
solve(N,X,Y,1);
return (ans/2+mod2)%mod2;
}
