#include <bits/stdc++.h>
#define forn(i, a, b) for(int i = int (a); i <= int(b); ++ i)
#define fora(i, a, b) for(int i = int (a); i >= int(b); -- i)
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
int mx[4] = {0, 0, 1, -1};
int my[4] = {1, -1, 0, 0};
map<pii, int> mapa;
queue<int> q;
const int maxn = 1e5;
int distancia[maxn];
vi graph[maxn];
int mod = 1e9;
int res = 0;
void bfs(int ind){
int u;
while(!q.empty()){
u = q.front();
q.pop();
for(auto v : graph[u]){
if(distancia[v] == -1){
distancia[v] = distancia[u] + 1;
if(v > ind){
res += distancia[v];
res %= mod;
}
q.push(v);
}
}
}
}
int DistanceSum(int N, int *X, int *Y) {
forn(i, 0, N - 1){
mapa[mp(X[i], Y[i])] = i;
}
forn(i, 0, N - 1){
forn(j, 0, 3){
if(mapa.count(mp(X[i] + mx[j], Y[i] + my[j]))){
graph[i].pb(mapa[mp(X[i] + mx[j], Y[i] + my[j])]);
}
}
}
forn(i, 0, N - 1){
memset(distancia, -1, sizeof(distancia));
distancia[i] = 0;
q.push(i);
bfs(i);
}
return res;
}
