#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000000;
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
int up[100010];
int us[100010];
int root(int x)
{
return x == up[x] ? x : (up[x] = root(up[x]));
}
bool merge(int x, int y)
{
x = root(x);
y = root(y);
if(x == y)
return 0;
up[x] = y;
us[y] += us[x];
us[x] = 0;
return 1;
}
int N;
int *X, *Y;
vector<int> edg[100010];
int siz[100010];
int f(int x, int p)
{
int r = 0;
siz[x] = us[x];
for(int y : edg[x])
{
if(y == p)
continue;
r = (r + f(y, x)) % mod;
siz[x] += siz[y];
}
for(int y : edg[x])
{
if(y == p)
continue;
r = (r + 1LL * siz[y] * (N - siz[y])) % mod;
}
return r;
}
int solve()
{
memset(siz, 0, sizeof siz);
for(int i = 0; i < N; i++)
{
up[i] = i;
us[i] = 1;
edg[i].clear();
}
map<pair<int, int>, int> m;
for(int i = 0; i < N; i++)
m[{ X[i], Y[i] }] = i;
vector<pair<int, int>> tmp;
for(int i = 0; i < N; i++)
{
for(int d = 0; d < 4; d++)
{
int nx = X[i] + dx[d];
int ny = Y[i] + dy[d];
auto it = m.find({ nx, ny });
if(it != m.end())
{
if(d % 2 == 0)
merge(i, it->second);
else
tmp.push_back({ i, it->second });
}
}
}
for(auto p : tmp)
{
int x, y;
tie(x, y) = p;
x = root(x);
y = root(y);
assert(x != y);
edg[x].push_back(y);
edg[y].push_back(x);
}
for(int i = 0; i < N; i++)
{
sort(edg[i].begin(), edg[i].end());
edg[i].erase(unique(edg[i].begin(), edg[i].end()), edg[i].end());
}
return f(root(1), -1);
}
int DistanceSum(int AN, int *AX, int *AY)
{
N = AN;
X = AX;
Y = AY;
int ans1 = solve();
for(int i = 0; i < N; i++)
swap(X[i], Y[i]);
int ans2 = solve();
return (ans1 + ans2) % mod;
}
