#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> p;
const int mod = 1e9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int uf[101010];
int size[101010];
int chk[101010];
int n;
set<int> g[101010];
int find(int v){
return uf[v] == v ? v : uf[v] = find(uf[v]);
}
void merge(int u, int v){
u = find(u), v = find(v);
if(u^v) uf[u] = v;
}
void dfs(int now, int prv, int &dist){ //거리 구하기
for(auto nxt : g[now]){
if(nxt^prv && !chk[nxt]){
chk[nxt] = 1;
dfs(nxt, now, dist);
size[now] += size[nxt];
}
}
ll tmp = (ll)size[now] * (ll)(n - size[now]);
tmp %= mod;
dist += tmp; dist %= mod;
}
int getDist(){
int ret = 0;
chk[find(0)+1] = 1;
for(int i=0; i<n; i++) size[find(i)+1]++;
dfs(find(0)+1, 0, ret);
return ret;
}
void makeTree(vector<p> &v){
//init
map<p, int> mp;
sort(v.begin(), v.end());
memset(size, 0, sizeof size);
memset(chk, 0, sizeof chk);
for(int i=0; i<n; i++) g[i].clear();
for(int i=0; i<=n+1; i++) uf[i] = i;
//union
for(int i=0; i<n-1; i++){
if(v[i].x == v[i+1].x && v[i].y+1 == v[i+1].y){
merge(i, i+1);
}
}
for(int i=0; i<n; i++){
mp[{v[i].x, v[i].y}] = find(i)+1;
}
//make
for(int i=0; i<n; i++){
int x = v[i].x, y = v[i].y;
for(int k=0; k<4; k++){
int xx = x + dx[k], yy = y + dy[k];
int nxt = mp[{xx, yy}];
if(nxt != 0 && find(i)+1 != nxt) g[find(i)+1].insert(nxt);
}
}
}
int DistanceSum(int N, int *X, int *Y){
n = N;
int ret = 0;
vector<p> v(n);
for(int i=0; i<n; i++){
v[i] = {X[i], Y[i]};
}
makeTree(v);
ret += getDist() % mod;
for(int i=0; i<n; i++){
v[i] = {Y[i], X[i]};
}
makeTree(v);
ret += getDist() % mod;
ret %= mod;
return ret;
}
