#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1'000'000'000;
vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int DistanceSum(int N, int *X, int *Y) {
// cerr << "!!! BRUTE SOLUTION " << endl;
map<pair<int, int>, int> cell_index;
for (int i = 0; i < N; ++i) cell_index[{X[i], Y[i]}] = i;
vector<vector<int>> graph(N);
for (int i = 0; i < N; ++i) {
for (auto [dx, dy] : dirs) {
int nx = X[i] + dx, ny = Y[i] + dy;
auto possible_index = cell_index.find({nx, ny});
if (possible_index != cell_index.end()) {
graph[i].push_back(possible_index->second);
}
}
}
ll ans = 0;
for (int i = 0; i < N; ++i) {
vector<int> dist(N, -1);
dist[i] = 0;
queue<int> q;
q.push(i);
while (!q.empty()) {
int cur = q.front(); q.pop();
for (int nxt : graph[cur]) {
if (dist[nxt] != -1) continue;
dist[nxt] = dist[cur] + 1;
q.push(nxt);
}
}
ans += accumulate(dist.begin(), dist.end(), 0LL);
}
return ans / 2 % MOD;
}
