#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define all(x) (x).begin(),(x).end()
const ll MAXN = 1e5 + 10;
const ll MOD = 1000000000;
int n;
vector<pll> vec;
ll ans = 0, dist[MAXN];
vector<int> adj[MAXN];
inline int get(ll x, ll y) {
pll e = pll(x, y);
auto it = lower_bound(all(vec), e);
if (it != vec.end() && *it == e) return it - vec.begin() + 1;
return 0;
}
inline void BFS(int v) {
memset(dist, 63, sizeof dist);
dist[v] = 0;
queue<int> q;
q.push(v);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int u : adj[v]) {
if (dist[v] + 1 < dist[u]) {
dist[u] = dist[v] + 1;
q.push(u);
}
}
}
}
int DistanceSum(int N, int *X, int *Y) {
n = N;
for (int i = 0; i < n; i++)
vec.push_back({X[i], Y[i]});
sort(all(vec));
for (int i = 1; i <= n; i++) {
int x = vec[i - 1].X, y = vec[i - 1].Y;
int j = get(x - 1, y);
if (j) adj[i].push_back(j);
j = get(x, y - 1);
if (j) adj[i].push_back(j);
j = get(x + 1, y);
if (j) adj[i].push_back(j);
j = get(x, y + 1);
if (j) adj[i].push_back(j);
}
for (int i = 1; i <= n; i++) {
BFS(i);
for (int j = i + 1; j <= n; j++)
ans = (ans + dist[j]) % MOD;
}
return ans % MOD;
}
