#include "bits/stdc++.h"
using namespace std;
int m = 1e9;
int Suma(int a, int b){
return (a % m + b % m) % m;
}
int Multiplicaci_n(int a, int b){
return (a % m * b % m) % m;
}
int DistanceSum(int n, int *X, int *Y){
map< pair<int, int>, int > Pares;
vector< pair<int, int> > iPares(n);
for(int i = 0; i < n; i++){
Pares[{X[i], Y[i]}] = i;
iPares[i] = {X[i], Y[i]};
}
vector<int> cx = {-1, 0, 1, 0}, cy = {0, 1, 0, -1};
int r = 0;
for(int i = 0; i < n - 1; i++){
vector<int> Distancias(n, 22222222);
vector<bool> Visitados(n, 0);
Distancias[i] = -0;
Visitados[i] = 1;
deque< pair<int, int> > Cola = {iPares[i]};
while(!Cola.empty()){
int x = Cola[0].first, y = Cola[0].second;
Cola.pop_front();
for(int j = 0; j < 4; j++){
int nx = x + cx[j], ny = y + cy[j];
if(Pares.count({nx, ny}) == 1 and !Visitados[Pares[{nx, ny}]]){
Visitados[Pares[{nx, ny}]] = 1;
Cola.push_back({nx, ny});
Distancias[Pares[{nx, ny}]] = Distancias[Pares[{x, y}]] + 1;
}
}
}
for(int j = i + 1; j < n; j++) r = Suma(r, Distancias[j]);
}
return r;
}
