#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int mod = 1e9;
int cntx[100000 + 10];
ll ans = 0;
ll n = 0;
int vis[100000 + 10];
ll dfs(int no, int fat, vector<vector<int>> &ed){
ll nodessum = cntx[no];
//cout << no << " " << fat << endl;
vis[no] = 1;
for(auto e:ed[no]){
if(e == fat || vis[e] == 1)continue;
ll su = dfs(e, no, ed);
nodessum += su;
ans += (n - su) * (su);
ans %= mod;
}
return nodessum;
}
void coordinate(map<pair<int, int>, int> &nodesy){
int cnt = 0;
pair<int, int> last = {-1, -1};
map<int, int> bigx;
memset(cntx, 0, sizeof cntx);
memset(vis, 0, sizeof vis);
for(auto e:nodesy){
if(last == (pair<int, int>){-1, -1}){
last = e.first;
bigx[e.second] = cnt;
cntx[cnt]++;
continue;
}else{
if(last.first == e.first.first &&last.second == e.first.second-1){
bigx[e.second] = cnt;
cntx[cnt]++;
last = e.first;
}else{
cnt++;
last = e.first;
bigx[e.second] = cnt;
cntx[cnt]++;
}
}
}
vector<vector<int>> edx(100005);
int start = 0;
for(auto e:nodesy){
int truenode = bigx[e.second];
start = truenode;
if(nodesy.count((pair<int, int>){e.first.first+1, e.first.second})){
edx[truenode].push_back(bigx[nodesy[{e.first.first+1, e.first.second}]]);
}
if(nodesy.count((pair<int, int>){e.first.first-1, e.first.second})){
edx[truenode].push_back(bigx[nodesy[{e.first.first-1, e.first.second}]]);
}
}
dfs(start, -1, edx);
//cout << ans << endl;
}
int DistanceSum(int N, int *X, int *Y) {
n = N;
memset(cntx, 0, sizeof cntx);
memset(vis, 0, sizeof vis);
map<pair<int, int>, int> nodesx;
map<pair<int, int>, int> nodesy;
for(int i = 0; i < N; ++i){
nodesx[{X[i], Y[i]}] = i;
nodesy[{Y[i], X[i]}] = i;
}
coordinate(nodesy);
coordinate(nodesx);
return ans % mod;
}
