#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
using namespace std;
vector<pii> dir = {{0,1},{1,0},{-1,0},{0,-1}};
map<pii,bool> ar,v;
ll bfs(int sx, int sy) {
v.clear();
ll ans = 0;
queue<pair<pii,int>> nxt;
nxt.push({{sx,sy},0});
while (!nxt.empty()) {
auto tmp = nxt.front();
nxt.pop();
if (v[tmp.f]) continue;
v[tmp.f] = 1;
ans += tmp.s;
for (auto i : dir) {
if (!v[{tmp.f.f+i.f, tmp.f.s+i.s}] && ar[{tmp.f.f+i.f, tmp.f.s+i.s}]) {
nxt.push({{tmp.f.f+i.f, tmp.f.s+i.s}, tmp.s+1});
}
}
}
return ans;
}
int DistanceSum(int N, int *X, int *Y) {
ll ans = 0;
for (int i = 0; i < N; i++) ar[{X[i],Y[i]}] = 1;
for (int i = 0; i < N; i++) {
ans += bfs(X[i],Y[i]);
}
return (ans/2) % 1'000'000'000;
}
