#include <bits/stdc++.h>
//#include "Lgrader.cpp"
using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
const int mod = (int)1e9;
int answer;
vector<pair<int, int> > S;
int gS(pair<int, int> x) { return lower_bound(S.begin(), S.end(), x) - S.begin() + 1; }
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};
vector<int> adj[MAXN];
int par[MAXN], sz[MAXN];
int root(int u) { return u == par[u] ? u : par[u] = root(par[u]); }
void unite(int u, int v)
{
u = root(u), v = root(v);
if(u == v) return;
if(sz[u] > sz[v])
swap(u, v);
sz[v] += sz[u];
par[u] = v;
}
int dp[MAXN];
void pre_dfs(int u, int pr)
{
dp[u] = sz[root(u)];
for(int v: adj[u])
if(v != pr)
{
pre_dfs(v, u);
dp[u] = (dp[u] + dp[v]) % mod;
}
}
int n;
void dfs(int u, int pr)
{
if(u != pr)
{
int curr = 0;
curr = (dp[u] * 1ll * (n - dp[u])) % mod;
answer = (answer + curr) % mod;
}
for(int v: adj[u])
if(v != pr)
dfs(v, u);
}
int DistanceSum(int N, int *X, int *Y)
{
::n = N;
answer = 0;
vector<pair<int, int> > li;
for(int i = 0; i < N; i++)
li.push_back({X[i], Y[i]});
int r, idx = 0;
for(auto it: li)
S.push_back(it);
sort(S.begin(), S.end());
li = S;
for(int i = 1; i <= n; i++) adj[i].clear();
for(int i = 1; i <= n; i++)
par[i] = i, sz[i] = 1;
idx = 0;
for(auto it: li)
{
idx++;
for(int d = 0; d < 2; d++)
{
pair<int, int> nxt = {dx[d] + it.first, dy[d] + it.second};
int oth = gS(nxt);
if(oth != (int)S.size() + 1 && S[oth - 1] == nxt)
unite(idx, oth);
}
}
idx = 0;
for(auto it: li)
{
idx++;
for(int d = 2; d < 4; d++)
{
pair<int, int> nxt = {dx[d] + it.first, dy[d] + it.second};
int oth = gS(nxt);
if(oth != (int)S.size() + 1 && S[oth - 1] == nxt)
adj[root(idx)].push_back(root(oth));
}
}
for(int i = 1; i <= n; i++)
{
sort(adj[i].begin(), adj[i].end());
adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
}
r = root(1);
pre_dfs(r, r);
dfs(r, r);
for(int i = 1; i <= n; i++) adj[i].clear();
for(int i = 1; i <= n; i++)
par[i] = i, sz[i] = 1;
idx = 0;
for(auto it: li)
{
idx++;
for(int d = 2; d < 4; d++)
{
pair<int, int> nxt = {dx[d] + it.first, dy[d] + it.second};
int oth = gS(nxt);
if(oth != (int)S.size() + 1 && S[oth - 1] == nxt)
unite(idx, oth);
}
}
idx = 0;
for(auto it: li)
{
idx++;
for(int d = 0; d < 2; d++)
{
pair<int, int> nxt = {dx[d] + it.first, dy[d] + it.second};
int oth = gS(nxt);
if(oth != (int)S.size() + 1 && S[oth - 1] == nxt)
adj[root(idx)].push_back(root(oth));
}
}
for(int i = 1; i <= n; i++)
{
sort(adj[i].begin(), adj[i].end());
adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
}
r = root(1);
pre_dfs(r, r);
dfs(r, r);
return answer;
}
