#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9;
const int M = 1e5 + 10;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};
vector<int> adj[M];
int comp[M], w[M], sub[M];
int ans = 0;
void dfs(int u, int par) {
sub[u] = w[u];
for(int v : adj[u]) if(v - par) {
dfs(v, u);
sub[u] += sub[v];
if(sub[u] >= mod)
sub[u] -= mod;
}
}
void solve(int N, int *X, int *Y) {
vector<pair<int, int> > v;
map<pair<int, int>, int> mp;
for(int i = 0; i < N; i++)
v.emplace_back(X[i], Y[i]);
sort(v.begin(), v.end());
for(int i = 0; i < N; i++)
mp[{v[i].first, v[i].second}] = i;
int idx = 0;
for(int i = 0; i < N; ) {
int x = v[i].first, j = i + 1;
comp[i] = idx;
while(j < N && v[j].second == v[j - 1].second + 1)
comp[j++] = idx;
w[idx++] = j - i;
i = j;
}
set<pair<int, int> > st;
for(int i = 0; i < N; i++) {
int x = v[i].first, y = v[i].second;
for(int j = 0; j < 4; j++) {
int xx = x + dx[j], yy = y + dy[j];
if(mp.count({xx, yy})) {
int a = comp[i], b = comp[mp[{xx, yy}]];
if(a > b) swap(a, b);
if(a != b) st.insert({a, b});
}
}
}
for(int i = 0; i < idx; i++)
adj[i].clear();
for(auto it : st) {
int u = it.first, v = it.second;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(0, -1);
for(int i = 1; i < idx; i++) {
ans += sub[i] * 1ll * (N - sub[i]) % mod;
if(ans >= mod) ans -= mod;
}
}
int DistanceSum(int N, int *X, int *Y) {
solve(N, X, Y);
solve(N, Y, X);
return ans;
}
