#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
using ii = pair<int, int>;
int dist[100005], dx[] = {-1, 0, 0, 1}, dy[] = {0, -1, 1, 0};
bool vis[100005];
map<ii, int> mpp;
queue<ii> Q;
const int MOD = (int)1e9;
int DistanceSum(int N, int X[], int Y[]) {
int ans = 0;
for (int i = 0; i < N; i++) {
mpp[mp(X[i], Y[i])] = i;
}
for (int i = 0; i < N; i++) {
Q.emplace(X[i], Y[i]);
for (int j = 0; j < N; j++) vis[j] = 0;
vis[i] = 1;
dist[i] = 0;
while (!Q.empty()) {
auto [x, y] = Q.front();
Q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k], ny = y + dy[k];
if (mpp.find(mp(nx, ny)) != mpp.end()) {
int idx = mpp[mp(nx, ny)];
if (!vis[idx]) {
vis[idx] = 1;
dist[idx] = dist[mpp[mp(x, y)]] + 1;
ans = (ans + dist[idx]) % MOD;
Q.emplace(X[idx], Y[idx]);
}
}
}
}
}
return ans / 2;
}
