#include <bits/stdc++.h>
#define ALL(x) x.begin(),x.end()
#define mod 1000000000
using namespace std;
typedef long long ll;
vector<pair<ll,ll>> puntos;
ll minix=2e9,miniy=2e9;
ll dist[2002][2002];
bool existe[2002][2002];
ll tot;
vector<pair<ll,ll>> bound_nivel;
vector<ll> res_temp,res_abs;
vector<ll> psum_nivel;
ll sumar(ll x,ll y){
if(x>y){
return 0;
}
ll cant=y-x+1;
return ((1+cant)*cant/2)%mod;
}
ll DistanceSum(int N,int *X,int *Y){
if(N<=2000){
puntos.resize(N);
for(ll i=0;i<N;i++){
puntos[i]={X[i],Y[i]};
minix=min(minix,(ll)(X[i]-1));
miniy=min(miniy,(ll)(Y[i]-1));
}
for(ll i=0;i<N;i++){
puntos[i].first-=minix;
puntos[i].second-=miniy;
existe[puntos[i].first][puntos[i].second]=true;
}
for(ll i=0;i<N;i++){
//bfs
ll suma=0;
queue<pair<ll,ll>> bfs;
bfs.push(puntos[i]);
while(!bfs.empty()){
pair<ll,ll> top=bfs.front();
bfs.pop();
suma+=dist[top.first][top.second];
if(dist[top.first-1][top.second]==0 && existe[top.first-1][top.second]){
dist[top.first-1][top.second]=dist[top.first][top.second]+1;
bfs.push({top.first-1,top.second});
}
if(dist[top.first+1][top.second]==0 && existe[top.first+1][top.second]){
dist[top.first+1][top.second]=dist[top.first][top.second]+1;
bfs.push({top.first+1,top.second});
}
if(dist[top.first][top.second-1]==0 && existe[top.first][top.second-1]){
dist[top.first][top.second-1]=dist[top.first][top.second]+1;
bfs.push({top.first,top.second-1});
}
if(dist[top.first][top.second+1]==0 && existe[top.first][top.second+1]){
dist[top.first][top.second+1]=dist[top.first][top.second]+1;
bfs.push({top.first,top.second+1});
}
}
tot+=suma-2;
bfs.push(puntos[i]);
dist[puntos[i].first][puntos[i].second]=0;
while(!bfs.empty()){
pair<ll,ll> top=bfs.front();
bfs.pop();
if(dist[top.first-1][top.second]!=0){
dist[top.first-1][top.second]=0;
bfs.push({top.first-1,top.second});
}
if(dist[top.first+1][top.second]!=0){
dist[top.first+1][top.second]=0;
bfs.push({top.first+1,top.second});
}
if(dist[top.first][top.second-1]!=0){
dist[top.first][top.second-1]=0;
bfs.push({top.first,top.second-1});
}
if(dist[top.first][top.second+1]!=0){
dist[top.first][top.second+1]=0;
bfs.push({top.first,top.second+1});
}
}
}
return tot/2;
}else{
res_temp.resize(N);
res_abs.resize(N);
puntos.resize(N);
psum_nivel.resize(N);
bound_nivel.assign(N,{1e9,-1e9});
for(ll i=0;i<N;i++){
puntos[i]={X[i],Y[i]};
minix=min(minix,(ll)X[i]);
miniy=min(miniy,(ll)Y[i]);
}
for(ll i=0;i<N;i++){
puntos[i].first-=minix;
puntos[i].second-=miniy;
bound_nivel[puntos[i].first].first=min(bound_nivel[puntos[i].first].first,puntos[i].second);
bound_nivel[puntos[i].first].second=max(bound_nivel[puntos[i].first].second,puntos[i].second);
}
sort(ALL(puntos));
psum_nivel[0]=bound_nivel[0].second-bound_nivel[0].first+1;
for(ll i=1;i<N;i++){
psum_nivel[i]=psum_nivel[i-1]+bound_nivel[i].second-bound_nivel[i].first+1;
}
/*for(ll i=0;i<N;i++){
//cout << bound_nivel[i].first << ' ' << bound_nivel[i].second << '\n';
//cout << psum_nivel[i] << '\n';
}*/
ll i=0;
for(;i<N;i++){
if(puntos[i].first==0){
res_abs[i]=sumar(bound_nivel[0].first,puntos[i].second-1)+sumar(puntos[i].second+1,bound_nivel[0].second);
res_abs[i]%=mod;
}else{
break;
}
}
for(;i<N;i++){
if(binary_search(ALL(puntos),make_pair(puntos[i].first-1,puntos[i].second))){
res_abs[i]=res_abs[lower_bound(ALL(puntos),make_pair(puntos[i].first-1,puntos[i].second))-puntos.begin()];
res_abs[i]+=psum_nivel[puntos[i].first-1];
res_abs[i]%=mod;
res_abs[i]+=sumar(puntos[i].second+1,bound_nivel[puntos[i].first].second);
res_abs[i]%=mod;
res_abs[i]+=sumar(bound_nivel[puntos[i].first].first,puntos[i].second-1);
res_abs[i]%=mod;
}else{
/*
caso:
.**.
****
***.
*/
ll pos=lower_bound(ALL(puntos),make_pair(puntos[i].first-1,0ll))-puntos.begin();
ll nuepos=lower_bound(ALL(puntos),make_pair(puntos[i].first-1,puntos[i].second))-puntos.begin();
nuepos--;
if(nuepos>=0){
if(puntos[nuepos].first==puntos[i].first-1){
pos=nuepos;
}
}
res_abs[i]=res_abs[pos];
res_abs[i]+=(abs(puntos[i].first-puntos[pos].first)+abs(puntos[i].second-puntos[pos].second))*psum_nivel[puntos[pos].first];
res_abs[i]%=mod;
res_abs[i]+=sumar(puntos[i].second+1,bound_nivel[puntos[i].first].second);
res_abs[i]%=mod;
res_abs[i]+=sumar(bound_nivel[puntos[i].first].first,puntos[i].second-1);
res_abs[i]%=mod;
}
}
for(ll i=0;i<N;i++){
//cout << res_abs[i] << '\n';
res_temp[i]=res_abs[i];
res_temp[i]-=sumar(bound_nivel[puntos[i].first].first,puntos[i].second-1);
res_temp[i]%=mod;
res_temp[i]+=mod;
res_temp[i]%=mod;
//res_temp[i]-=sumar(puntos[i].second+1,bound_nivel[puntos[i].first].second);
tot+=res_temp[i];
tot%=mod;
}
/*for(ll i=0;i<N;i++){
tot+=sumar(bound_nivel[i].first,bound_nivel[i].second);
}*/
return tot;
}
}
