#include "bits/stdc++.h"
using namespace std;
const int md = (int) 1e9;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int DistanceSum(int N, int *X, int *Y) {
int ret = 0;
map<pair<int, int>, int> cells;
for (int i = 0; i < N; ++i) {
cells[make_pair(X[i], Y[i])] = i;
}
for (int i = 0; i < N; ++i) {
queue<pair<int, int>> que;
map<pair<int, int>, int> mp;
que.emplace(X[i], Y[i]);
mp[make_pair(X[i], Y[i])] = 0;
while (!que.empty()) {
auto [x, y] = que.front();
que.pop();
if (cells[make_pair(x, y)] < i) {
ret += mp[make_pair(x, y)];
ret %= md;
}
for (int k = 0; k < 4; ++k) {
int nx = x + dx[k], ny = y + dy[k];
if (cells.count(make_pair(nx, ny)) && !mp.count(make_pair(nx, ny))) {
mp[make_pair(nx, ny)] = mp[make_pair(x, y)] + 1;
que.emplace(nx, ny);
}
}
}
}
return ret;
}
