#include <bits/stdc++.h>
#define entire(X) X.begin(),X.end()
using namespace std; typedef long long ll;
void OJize(){cin.tie(NULL); ios_base::sync_with_stdio(false);}
vector<int> bfs(vector<vector<int>> &adj, int v){
vector<int> dist(adj.size(), -1); dist[v] = 0;
queue<int> Q({v});
while(!Q.empty()){
int p = Q.front(); Q.pop();
for(int q: adj[p]) if(dist[q] == -1){
dist[q] = dist[p] + 1;
Q.push(q);
}
}
return dist;
}
const int MOD = 1000000000;
int DistanceSum(int N, int *X, int *Y){
assert (N <= 2000);
vector<vector<int>> adj(N);
for(int i=0; i<N; i++) for(int j=i+1; j<N; j++){
if(abs(X[i]-X[j]) + abs(Y[i]-Y[j]) > 1) continue;
adj[i].push_back(j), adj[j].push_back(i);
}
int ans = 0;
for(int i=0; i<N; i++){
vector<int> dist = bfs(adj, i);
for(int j=i+1; j<N; j++) ans = (ans + dist[j]) % MOD;
}
return ans;
}
