#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cns = 1e9;
vector<vector<ll>> adjlist;
vector<ll> comsize;
ll comtot;
ll f(ll a, ll b){
return a*cns+b;
}
ll dfs(ll node, ll parent){
ll ans = 0;
for (ll i : adjlist[node]){
if (i==parent){continue;}
ans += dfs(i,node);
ans += comsize[i]*(comtot-comsize[i]);
comsize[node]+=comsize[i];
}
//cout<<comsize[node]<<endl;
//cout<<node<<' '<<parent<<' '<<comsize[node]<<'\n';
return ans;
}
ll getSum(vector<pair<ll,ll>> &coords){
ll curcom = 0;
ll cursize = 0;
vector<pair<ll,ll>> edgelist;
adjlist.clear();
comsize.clear();
comtot = 0;
unordered_map<ll,ll> visx;
for (auto c : coords){
if (cursize!=0&&visx.find(f(c.first-1,c.second))==visx.end()){
comsize.push_back(cursize);
comtot+=cursize;
curcom++;
cursize = 0;
}
cursize++;
if (visx.find(f(c.first,c.second-1))!=visx.end()){
edgelist.push_back({visx[f(c.first,c.second-1)],curcom});
//cout<<visx[f(c.first,c.second-1)]<<' '<<curcom<<endl;
}
visx[f(c.first,c.second)]=curcom;
//cout<<c.first<<' '<<c.second<<": "<<curcom<<endl;
}
comsize.push_back(cursize);
comtot+=cursize;
//cout<<comtot<<endl;
/*for (ll i : comsize){
cout<<i<<' ';
}cout<<endl;*/
curcom++;
sort(edgelist.begin(),edgelist.end());
edgelist.erase(unique(edgelist.begin(),edgelist.end()),edgelist.end());
adjlist.resize(curcom);
assert(comsize.size()==adjlist.size());
for (auto e : edgelist){
adjlist[e.first].push_back(e.second);
adjlist[e.second].push_back(e.first);
}
//cout<<"bleh"<<endl;
return dfs(0,-1);
}
int DistanceSum(int n, int *X, int *Y) {
vector<pair<ll,ll>> coords(n);
for (ll i = 0; i<n; i++){
coords[i]={X[i],Y[i]};
}
sort(coords.begin(),coords.end(),[](pair<ll,ll> a, pair<ll,ll> b){return a.second==b.second?a.first<b.first:a.second<b.second;});
ll tmpans = 0;
tmpans+=getSum(coords);
for (ll i = 0; i<n; i++){
coords[i]={coords[i].second,coords[i].first};
}
sort(coords.begin(),coords.end(),[](pair<ll,ll> a, pair<ll,ll> b){return a.second==b.second?a.first<b.first:a.second<b.second;});
tmpans+=getSum(coords);
return (tmpans)%1000000000;
}
