#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef pair<int, int> point;
#define x first
#define y second
const lld MOD = 1000000000;
int A[100000];
point T[100000];
int B[100000];
vector<point> L[100000];
lld ans = 0;
vector<int> adj[100000];
bool chk[100000];
bool vis[100000];
int M;
void init(){
memset(A, 0, sizeof(A));
memset(B, 0, sizeof(B));
for (int i=0; i<100000; i++){
L[i].clear();
T[i] = point(0, 0);
adj[i].clear();
}
memset(chk, 0, sizeof(chk));
memset(vis, 0, sizeof(vis));
}
int dfs(int i){
vis[i] = 1;
int ret = 0;
for (int j: adj[i])
if (!vis[j])
ret += dfs(j);
ret += L[i].size();
ans = (ans + 1LL*ret*(M-ret))%MOD;
return ret;
}
void compute_dist(int N, int *X, int *Y){
M = N;
for (int i=0; i<N; i++){
T[i] = point(X[i], Y[i]);
}
sort(T, T+N);
L[0].push_back(T[0]);
int tot = 0;
for (int i=1; i<N; i++){
if (L[tot].back().x == T[i].x && L[tot].back().y + 1 == T[i].y)
L[tot].push_back(T[i]);
else
L[++tot].push_back(T[i]);
B[i] = tot;
}
++tot;
int s = 1, e = 1;
for (int i=0; i<tot; i++){
while (true){
if (s == tot) break;
if (L[s][0].x <= L[i][0].x) s++;
else{
if (L[i][0].x + 1 == L[s][0].x && L[s].back().y < L[i][0].y) s++;
else break;
}
}
while (true){
if (e == tot) break;
if (L[e][0].x <= L[i][0].x) e++;
else{
if (L[i][0].x + 1 == L[e][0].x && L[e][0].y <= L[i].back().y) e++;
else break;
}
}
for (int j=s; j<e; j++){
adj[i].push_back(j);
adj[j].push_back(i);
}
}
dfs(0);
}
int DistanceSum(int N, int *X, int *Y) {
compute_dist(N, X, Y);
init();
compute_dist(N, Y, X);
return ans;
}
