#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
#define ll long long
using namespace std;
ll MOD =1000000000;
ll maxx = pow(2,31)-2;
bool visited[2500][2500];
bool state[2500][2500];
bool deactivated[2500][2500];
int DistanceSum(int N, int *X, int *Y) {
memset(visited,0,sizeof visited);
memset(state, false, sizeof state);
memset(deactivated, false, sizeof deactivated);
for (int i = 0; i < N;++i){
state[X[i]][Y[i]]=true;
}
ll c=0;
for (int i = 0; i < N;++i){
queue<pair<pair<int,int>,int>> kiwi;
kiwi.push(
{{X[i],Y[i]},0}
);
memset(visited,0,sizeof visited);
while (kiwi.size()>0){
pair<pair<int,int>,int> it = kiwi.front();kiwi.pop() ;
if (!visited[it.first.first][it.first.second]){
visited[it.first.first][it.first.second]=true;
if (!deactivated[it.first.first][it.first.second])c+=it.second;
pair<int,int> cords[]={
{1,0},
{0,1},
{0,-1},
{-1,0}
};
for (int j = 0 ; j <4;++j){
pair<int,int> cord = cords[j];
pair<int,int> newcords={it.first.first+cord.first,it.first.second+cord.second};
if (newcords.first>=0 && newcords.second>=0 && newcords.first <=maxx && newcords.second <=maxx){
if (state[newcords.first][newcords.second] && !visited[newcords.first][newcords.second]){
kiwi.push({newcords,it.second+1});
c = c % MOD;
}
}
}
}
}
deactivated[X[i]][Y[i]]=true;
}
return c;
}
