#include <bits/stdc++.h>
using namespace std;
#define ll long long
int coorX[2010];
int coorY[2010];
int MOD = 1000000000;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
map<pair<int, int>, int> mp;
ll bfs(int idx, int n) {
queue <int> q;
vector<bool> visited(2010,0);
vector<int> dist(2010, 0);
q.push(idx);
visited[idx]=1;
while (!q.empty()) {
int fr = q.front();
q.pop();
// cout << fr << " " << dist[fr] << endl;
int cx = coorX[fr];
int cy = coorY[fr];
for (int i = 0; i < 4; i++) {
int nx = cx+dx[i];
int ny = cy+dy[i];
if (mp.count(make_pair(nx, ny))) {
int nxt = mp[make_pair(nx, ny)];
if (visited[nxt] == 0) {
q.push(nxt);
dist[nxt] = dist[fr]+1;
visited[nxt] = 1;
}
}
}
}
ll sum =0 ;
for (int i = 0; i < idx; i++) {
sum += dist[i];
// cout << dist[i] << endl;
}
return sum;
}
int DistanceSum(int N, int *X, int *Y) {
for (int i = 0; i < N; i++) {
mp[make_pair(X[i], Y[i])] = i;
coorX[i] = X[i];
coorY[i] = Y[i];
}
ll sumtot = 0;
for (int i = 0; i < N; i++) {
sumtot += bfs(i, N);
sumtot %= MOD;
}
return sumtot;
}
