#include <bits/stdc++.h>
using namespace std;
#define mkp make_pair
int DistanceSum(int N, int *X, int *Y) {
map<pair<int,int>,bool> con;
for(int i=0;i<N;i++){
con[mkp(X[i],Y[i])]=true;
}
int ans=0;
vector<int> distx={1,0,-1,0},disty={0,1,0,-1};
for(int i=0;i<N;i++){
queue<pair<int,int>> q;
q.push(mkp(X[i],Y[i]));
map<pair<int,int>,int> dist;
dist[mkp(X[i],Y[i])]=0;
while(q.size()){
pair<int,int> nodo=q.front();
q.pop();
int d=dist[nodo];
for(int i=0;i<4;i++){
if(con.count(mkp(nodo.first-distx[i],nodo.second-disty[i]))==0 || dist.count(mkp(nodo.first-distx[i],nodo.second-disty[i])))continue;
q.push(mkp(nodo.first-distx[i],nodo.second-disty[i]));
dist[mkp(nodo.first-distx[i],nodo.second-disty[i])]=d+1;
}
}
for(int j=i+1;j<N;j++){
if (dist.count(mkp(X[j],Y[j]))) {
ans=(ans+dist[mkp(X[j],Y[j])])%1000000000;
}
}
}
return ans;
}
