#include <bits/stdc++.h>
using namespace std;
int city[2002][2002];
bool revisado[2002][2002];
int visto[2002][2002];
int vacio=1;
long long int suma=0;
int lim,origen;
queue<pair<long long int,int>> cola;
int col[2002], fil[2002];
void dfs(int i,int j){
cola.push({0,city[i][j]});
while(cola.size()>0){
pair<long long int,int> aux=cola.front();
cola.pop();
if(visto[fil[aux.second]][col[aux.second]]!=vacio){
visto[fil[aux.second]][col[aux.second]]=vacio;
if(revisado[min(aux.second,origen)][max(aux.second,origen)]==false){
revisado[min(aux.second,origen)][max(aux.second,origen)]=true;
suma+=(aux.first*-1);
suma%=1000000000;
}
i=fil[aux.second-1];
j=col[aux.second-1];
if(i<lim&&city[i+1][j]>0) cola.push({aux.first-1,city[i+1][j]});
if(i>1&&city[i-1][j]>0) cola.push({aux.first-1,city[i-1][j]});
if(j<lim&&city[i][j+1]>0) cola.push({aux.first-1,city[i][j+1]});
if(j>1&&city[i][j-1]>0) cola.push({aux.first-1,city[i][j-1]});
}
}
}
int DistanceSum(int N, int *X, int *Y) {
lim=N;
long long int total=0;
for(int i=0;i<N;i++){
fil[i]=X[i];
col[i]=Y[i];
city[X[i]][Y[i]]=i+1;
}
for(int i=0;i<N;i++){
suma=0;
origen=i+1;
dfs(X[i],Y[i]);
total+=suma;
total%=1000000000;
vacio++;
}
return total;
}
