#include <stdio.h>
#include <queue>
#include <map>
#include <algorithm>
#define ff first
#define ss second
#define LL long long
#define pll pair<LL,LL>
#define MOD 1000000000
using namespace std;
struct ci{
LL x,y;
int nea[4]={-1,-1,-1,-1};
}inf[2222];
LL n,sum;
LL x[2222],y[2222];
map<pll,int> mp;
queue<int> qi,qd;
bool is_gone[2222];
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
void bfs(int v,int d){
qi.push(v);
qd.push(d);
is_gone[v]=1;
while(!qi.empty()){
int pi=qi.front(); qi.pop();
int pd=qd.front(); qd.pop();
sum=(sum+pd)%(MOD*2);
for(int i=0;i<4;i++){
if(inf[pi].nea[i]!=-1 && !is_gone[inf[pi].nea[i]]){
qi.push(inf[pi].nea[i]);
qd.push(pd+1);
is_gone[inf[pi].nea[i]]=1;
}
}
}
}
int DistanceSum(int N,int *X,int *Y){
n=N;
for(int i=0;i<N;i++) x[i]=X[i];
for(int i=0;i<N;i++) y[i]=Y[i];
for(int i=0;i<n;i++) mp.insert({{x[i],y[i]},i});
for(int i=0;i<n;i++){
inf[i].x=x[i];
inf[i].y=y[i];
for(int j=0;j<4;j++){
int nx=x[i]+dx[j];
int ny=y[i]+dy[j];
map<pll,int>::iterator it=mp.find({nx,ny});
if(it!=mp.end()) inf[i].nea[j]=it->ss;
}
}
if(n<=2000){
/*
for(int i=0;i<n;i++){
printf("%2d %2d ",inf[i].x,inf[i].y);
for(int j=0;j<4;j++) printf("%2d ",inf[i].nea[j]);
printf("\n");
}
printf("\n");
*/
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) is_gone[j]=0;
bfs(i,0);
}
return sum/2;
}
return 0;
}
