#include <bits/stdc++.h>
using namespace std;
#define mkp make_pair
#define ll long long
ll sumM(vector<int>&A){
sort(A.begin(),A.end());
ll ans=0,sum=0;
for(int i=0;i<A.size();i++){
ans+=1LL*A[i]*i-sum;
sum+=A[i];
}
return ans%1000000000;
}
int DistanceSum(int N,int*X,int*Y){
if(N>2000){
vector<int> lnx(X,X+N),lny(Y,Y+N);
return (sumM(lnx)+sumM(lny))%1000000000;
}else{
map<pair<int,int>,int> nodes;
for(int i=0;i<N;i++){
nodes[mkp(X[i],Y[i])]=i;
}
vector<vector<int>> ln(N);
for(auto&e:nodes){
int x=e.first.first,y=e.first.second,i=e.second;
if(nodes.count(mkp(x+1,y)))ln[i].push_back(nodes[mkp(x+1,y)]);
if(nodes.count(mkp(x-1,y)))ln[i].push_back(nodes[mkp(x-1,y)]);
if(nodes.count(mkp(x,y+1)))ln[i].push_back(nodes[mkp(x,y+1)]);
if(nodes.count(mkp(x,y-1)))ln[i].push_back(nodes[mkp(x,y-1)]);
}
int ans=0;
for(int i=0;i<N;i++){
queue<int> q;
q.push(i);
vector<int> dist(N,-1);
dist[i]=0;
while(q.size()){
int nodo=q.front();q.pop();
for(int v:ln[nodo]){
if(dist[v]<0){
dist[v]=dist[nodo]+1;
q.push(v);
}
}
}
for(int j=i+1;j<N;j++){
if(dist[j]>=0){
ans=(ans+dist[j])%1000000000;
}
}
}
return ans;
}
}
