#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9;
struct DSU{
int path[100100];
void init(int n){
for (int i=1;i<=n;i++) path[i] = i;
}
int find(int x){
if (x==path[x]) return x;
return path[x] = find(path[x]);
}
void merge(int x, int y){
path[find(x)] = find(y);
}
}dsu;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int *X, *Y, n;
ll ans;
map<pair<int, int>, int> st;
bool adj[100100][4], visited[100100];
int dfs(int s){
//printf("%d\n", s);
visited[s] = 1;
int ret = 1;
for (int k=0;k<4;k++) if (adj[s][k]){
int nx = X[s] + dx[k], ny = Y[s] + dy[k];
int j = st[{nx, ny}];
if (visited[j]) continue;
int tmp = dfs(j);
if (k>1) ans = (ans+(ll)tmp*(n-tmp))%MOD;
ret += tmp;
}
return ret;
}
void build_st(){
dsu.init(n);
for (int i=1;i<=n;i++){
for (int j=0;j<4;j++) adj[i][j] = 0;
visited[i] = 0;
}
for (int i=1;i<=n;i++){
int x = X[i], y = Y[i];
int nx = x + dx[0], ny = y + dy[0];
int j = st[{nx, ny}];
if (j && dsu.find(i) != dsu.find(j)){
dsu.merge(i, j);
adj[i][0] = 1;
adj[j][1] = 1;
//printf(" %d %d\n", i, j);
}
}
for (int i=1;i<=n;i++){
int x = X[i], y = Y[i];
int nx = x + dx[2], ny = y + dy[2];
int j = st[{nx, ny}];
if (j && dsu.find(i) != dsu.find(j)){
dsu.merge(i, j);
adj[i][2] = 1;
adj[j][3] = 1;
//printf(" %d %d\n", i, j);
}
}
/*for (int i=1;i<=n;i++) printf("%d ", dsu.find(i));
printf("\n");*/
}
int DistanceSum(int N, int *x, int *y) {
ans = 0;
n = N;
X = x-1, Y = y-1;
for (int i=0;i<n;i++) st[{x[i], y[i]}] = i+1;
build_st();
dfs(st[{X[1], Y[1]}]);
dx[0] = 1, dx[1] = -1, dx[2] = 0, dx[3] = 0;
dy[0] = 0, dy[1] = 0, dy[2] = 1, dy[3] = -1;
build_st();
dfs(st[{X[1], Y[1]}]);
return ans;
}
