#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define trace(x) for (auto &a : x) cout << a << " ";
const int MOD = 1'000'000'000;
int n;
vector<int> x, y;
map<pair<int, int>, int> nmap;
vector<vector<int>> adj;
int bfs_sum(int node) {
int ans = 0;
vector<bool> vis(n, false);
vector<int> dist(n, 0);
queue<int> q; q.push(node);
while (!q.empty()) {
int cur = q.front();
q.pop();
vis[cur] = true;
for (int nei : adj[cur]) {
if (vis[nei]) continue;
dist[nei] = dist[cur] + 1;
q.push(nei);
}
}
FOR(i, node+1, n) {
ans += dist[i];
ans %= MOD;
}
return ans % MOD;
}
int DistanceSum(int _N, int *_X, int *_Y) {
n = _N;
x.resize(0); y.resize(0);
adj.assign(n, vector<int>());
for (int i = 0; i < n; i++) x.pb(_X[i]), y.pb(_Y[i]);
FOR(i, 0, n) {
nmap[{x[i], y[i]}] = i;
}
FOR(i, 0, n) {
FOR(dx, -1, 2) {
FOR(dy, -1, 2) {
if (abs(dx) == abs(dy)) continue;
if (!nmap.count({x[i] + dx, y[i] + dy})) continue;
adj[i].pb(nmap[{x[i] + dx, y[i] + dy}]);
}
}
}
int ans = 0;
// FOR(i, 0, n) {
// ans += bfs_sum(i);
// ans %= MOD;
// }
n = 0;
x.clear();
y.clear();
adj.clear();
nmap.clear();
return ans % MOD;
}
