#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define vi vector<ll>
#define fi first
#define se second
#define pb emplace_back
const ll mod = 1000000000;
int dx[] = {1,-1,0,0}, dy[] = {0,0,1,-1};
map<pii,int> vis;
ll dis[100005];
vi E[100005];
ll BFS(int x){
ll ans = 0;
queue<int> q;
q.push(x);
dis[x] = 0;
while(!q.empty()){
int nd = q.front(); q.pop();
for(auto &i:E[nd]){
if(dis[i] != -1) continue;
dis[i] = dis[nd]+1;
if(i > x) ans += dis[i];
ans %= mod;
q.push(i);
}
}
return ans;
}
int DistanceSum(int N, int *X, int *Y) {
for(int i=0;i<N;i++){
vis[{X[i],Y[i]}] = i+1;
for(int j=0;j<4;j++){
int nx = X[i] + dx[j], ny = Y[i] + dy[j];
int id = vis[{nx,ny}];
if(id){
E[i+1].pb(id);
E[id].pb(i+1);
}
}
}
ll ans = 0;
for(int i=1;i<=N;i++){
memset(dis, -1, sizeof(dis));
ans += BFS(i);
ans %= mod;
}
return ans;
}
