#include <bits/stdc++.h>
using ll =long long;
//#define int ll
ll LINF=1000000000000000000;
int INF=1000000000;
#define pi pair<int,int>
#define pl pair<ll,ll>
#define endl '\n'
#define vi vector<int>
#define vii vector<vector<int>>
#define vl vector<ll>
#define vll vector<vector<ll>>
//#define int ll
using namespace std;
int DistanceSum(int n,int *X,int *Y){
map<pi,int>m;
map<pi,pi>pos;
int mod=1e9;
vii g(n);
for(int i=0;i<n;i++){
m.insert(make_pair(make_pair(X[i],Y[i]),i));
}
for(int i=0;i<n;i++){
int x=X[i],y=Y[i];
auto itr=m.find(make_pair(x+1,y));
if(itr!=m.end()){
g[i].push_back(itr->second);
}
itr=m.find(make_pair(x-1,y));
if(itr!=m.end()){
g[i].push_back(itr->second);
}
itr=m.find(make_pair(x,y+1));
if(itr!=m.end()){
g[i].push_back(itr->second);
}
itr=m.find(make_pair(x,y-1));
if(itr!=m.end()){
g[i].push_back(itr->second);
}
}
ll result=0;
for(int i=0;i<n;i++){
set<pair<ll,int>>s;
s.insert(make_pair(0ll,i));
vi checked(n);
while(!s.empty()){
ll dist=s.begin()->first;
dist%=mod;
int node=s.begin()->second;
checked[node]= 1;
result+=dist;
result%=mod;
s.erase(s.begin());
for(int &i:g[node]){
if(checked[i])continue;
s.insert(make_pair(dist+1,i));
}
}
}
return result/2;
}
