// And you curse yourself for things you never done
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
const int Nine = (int)1e9;
int arr[maxn];
pii scr[maxn];
int pr[maxn];
int fnd(int u){
return pr[u] < 0 ? u : pr[u] = fnd(pr[u]);
}
void mrg(int a, int b){
if( (a = fnd(a)) == (b = fnd(b)) )
return;
if(pr[a] > pr[b])
swap(a, b);
pr[a]+= pr[b];
pr[b] = a;
}
int solve(int n, int *X, int *Y){
int ans = 0;
map<pii, int> mp;
for(int i = 0; i < n; i++)
mp[{X[i], Y[i]}] = i;
auto cmp = [&](int i, int j){ return (pii){X[i], Y[i]} < (pii){X[j], Y[j]}; };
iota(arr, arr + n, 0);
sort(arr, arr + n, cmp);
memset(pr, -1, sizeof pr);
memset(scr, -1, sizeof scr);
int pt = 0;
while(pt < n){
int ptl = pt, ptr = pt;
while(ptr < n && X[arr[ptl]] == X[arr[ptr]])
ptr++;
pt = ptr;
for(int i = ptl; i < ptr; i++){
int x = X[arr[i]], y = Y[arr[i]];
for(pii p : { (pii){-1, 0}, (pii){0, 1}, (pii){0, -1} }){ // not x + 1
int xx = x + p.F, yy = y + p.S;
if(mp.count({xx, yy}))
mrg(arr[i], mp[{xx, yy}]);
}
}
for(int i = ptl; i < ptr; i++){
int x = X[arr[i]] + 1, y = Y[arr[i]];
if(mp.count({x, y}))
scr[mp[{x, y}]] = {-pr[fnd(arr[i])], fnd(arr[i])};
}
}
// Round 2
{
auto cmp = [&](int i, int j){ return (pii){-X[i], Y[i]} < (pii){-X[j], Y[j]}; };
sort(arr, arr + n, cmp);
memset(pr, -1, sizeof pr);
int pt = 0;
while(pt < n){
int ptl = pt, ptr = pt;
while(ptr < n && X[arr[ptl]] == X[arr[ptr]])
ptr++;
pt = ptr;
for(int i = ptl; i < ptr; i++){
int x = X[arr[i]], y = Y[arr[i]];
for(pii p : { (pii){1, 0}, (pii){0, 1}, (pii){0, -1} }){ // not x - 1
int xx = x + p.F, yy = y + p.S;
if(mp.count({xx, yy}))
mrg(arr[i], mp[{xx, yy}]);
}
}
set<pii> st;
for(int i = ptl; i < ptr; i++){
if(scr[ arr[i] ].F == -1)
continue;
int A = fnd(arr[i]), B = scr[ arr[i] ].S;
if(st.count({A, B}))
continue;
st.insert({A, B});
ans = (1ll * ans + 1ll * scr[ arr[i] ].F * (-pr[fnd(arr[i])])) % Nine;
}
}
}
return ans;
}
int ITER = 0;
int DistanceSum(int n, int *X, int *Y){
assert(++ITER <= 1);
return (solve(n, X, Y) + solve(n, Y, X)) % Nine;
}
