#include <bits/stdc++.h>
using namespace std;
#define mkp make_pair
int DistanceSum(int N,int*X,int*Y){
map<pair<int,int>,int> nodes;
for(int i=0;i<N;i++){
nodes[mkp(X[i],Y[i])]=i;
}
vector<vector<int>> ln(N);
for(auto&e:nodes){
int x=e.first.first,y=e.first.second,i=e.second;
if(nodes.count(mkp(x+1,y)))ln[i].push_back(nodes[mkp(x+1,y)]);
if(nodes.count(mkp(x-1,y)))ln[i].push_back(nodes[mkp(x-1,y)]);
if(nodes.count(mkp(x,y+1)))ln[i].push_back(nodes[mkp(x,y+1)]);
if(nodes.count(mkp(x,y-1)))ln[i].push_back(nodes[mkp(x,y-1)]);
}
int ans=0;
for(int i=0;i<N;i++){
queue<int> q;
q.push(i);
vector<int> dist(N,-1);
dist[i]=0;
while(q.size()){
int nodo=q.front();q.pop();
for(int v:ln[nodo]){
if(dist[v]<0){
dist[v]=dist[nodo]+1;
q.push(v);
}
}
}
for(int j=i+1;j<N;j++){
if(dist[j]>=0){
ans=(ans+dist[j])%1000000000;
}
}
}
return ans;
}
