#include <bits/stdc++.h>
#define int int64_t
#define pb push_back
#define mp(x...) array<int, 2>({x})
using namespace std;
constexpr static int MOD = 1e9;
static inline int add(int a, int b) { return (a+b) % MOD; }
static inline int mul(int64_t a, int64_t b) { return (a*b) % MOD; }
constexpr static int MXN = 2000;
int32_t n, *x, *y;
vector<int> g[MXN];
vector<array<int, 2>> nodes;
int find(int a, int b)
{
auto it = lower_bound(nodes.begin(), nodes.end(), mp(a, b));
if (it != nodes.end() && (*it)[0] == a && (*it)[1] == b)
return it - nodes.begin();
return -1;
}
void try_insert(int node, int a, int b)
{
int res = find(a, b);
if (res != -1)
g[node].pb(res);
}
int dist[MXN];
int bfs(int root)
{
for (int i = 0; i < n; i++)
dist[i] = -1;
queue<int> q;
dist[root] = 0;
q.push(root);
int res = 0;
while (q.size())
{
int node = q.front();
q.pop();
res += dist[node];
for (int c : g[node])
{
if (dist[c] == -1)
{
dist[c] = dist[node]+1;
q.push(c);
}
}
}
return res;
}
int32_t DistanceSum(int32_t N, int32_t *X, int32_t *Y)
{
x = X, y = Y;
n = N;
for (int i = 0; i < n; i++)
nodes.pb(mp(x[i], y[i]));
sort(nodes.begin(), nodes.end());
for (int i = 0; i < n; i++)
{
auto [x, y] = nodes[i];
try_insert(i, x+1, y);
try_insert(i, x-1, y);
try_insert(i, x, y+1);
try_insert(i, x, y-1);
}
int res = 0;
for (int i = 0; i < n; i++)
res += bfs(i);
return (res / 2) % MOD;
}
