/// Bravo Bodo plm
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int mod = int(1e9);
int N, ans;
void solve(int *X, int *Y)
{
map<pii, int> mp;
vector<pii> v;
for(int i = 0; i < N; i++) v.push_back({X[i], Y[i]});
sort(begin(v), end(v));
vector<int> g(N);
int G = 1;
g[0] = 0;
for(int i = 1; i < N; i++)
{
if(v[i].first == v[i - 1].first && v[i].second == v[i - 1].second + 1)
g[i] = g[i - 1];
else
g[i] = G++;
}
vector< vector<int> > edg(G);
vector<int> val(G);
for(int i = 0; i < N; i++)
{
mp[ v[i] ] = g[i];
val[ g[i] ]++;
}
map<pii, int> hasEdge;
for(int i = 0; i < N; i++)
{
int x = v[i].first, y = v[i].second, z = g[i];
auto addEdge = [&](int x, int y)
{
if(hasEdge.count({x, y})) return;
hasEdge[{x, y}] = hasEdge[{y, x}] = 1;
edg[x].push_back(y);
edg[y].push_back(x);
};
if(mp.count({x - 1, y}))
addEdge(z, mp[{x - 1, y}]);
if(mp.count({x + 1, y}))
addEdge(z, mp[{x + 1, y}]);
}
vector<int> sz(G);
function<void(int, int)> DFS = [&](int nod, int fth)
{
sz[nod] = val[nod];
for(auto nxt: edg[nod])
if(nxt != fth)
{
DFS(nxt, nod);
sz[nod] += sz[nxt];
}
};
DFS(0, -1);
int tot = sz[0];
for(int i = 0; i < G; i++)
{
ans += (1LL * sz[i] * (tot - sz[i])) % mod;
if(ans >= mod) ans -= mod;
}
}
int DistanceSum(int _N, int *X, int *Y)
{
N = _N, ans = 0;
solve(X, Y);
solve(Y, X);
return ans;
}
