#include <bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
#define eb emplace_back
using namespace std;
typedef long long ll;
using pii = pair<int, int>;
const ll MOD = 1000000000;
int n;
vector<vector<int>> g;
vector<pii> dir = {mp(1, 0), mp(0, 1), mp(-1, 0), mp(0, -1)};
ll bfs(int st){
vector<ll> dis(n, -1);
dis[st] = 0;
queue<int> q;
q.push(st);
ll ans = 0;
while(!q.empty()){
int now = q.front();
ans += dis[now];
q.pop();
for(int i : g[now]){
if(dis[i] != -1) continue;
dis[i] = dis[now] + 1;
q.push(i);
}
}
return ans;
}
int DistanceSum(int N, int *X, int *Y){
n = N;
g.resize(n);
map<pii, int> city;
for(int i = 0; i < n; i++){
city[mp(X[i], Y[i])] = i;
}
for(int i = 0; i < n; i++){
int x = X[i], y = Y[i];
for(pii d : dir){
int nx = x + d.F, ny = y + d.S;
if(city.find(mp(nx,ny)) == city.end()) continue;
g[i].eb(city[mp(nx,ny)]);
}
}
ll ans = 0;
for(int i = 0; i < n; i++) ans += bfs(i);
return ans / 2 % MOD;
}
