#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int mod = 1e9;
int bfs(int no, vector<vector<int>> &ed){
queue<int> q;
int vis[(int)ed.size()];
memset(vis, -1, sizeof vis);
q.push(no);
vis[no] = 0;
while((int)q.size() > 0){
int node = q.front();
q.pop();
for(auto e:ed[node]){
if(vis[e] == -1){
vis[e] = vis[node]+1;
q.push(e);
}
}
}
ll ans = 0;
for(int i = 0; i < no; ++i){
ans += vis[i];
ans %= mod;
}
return ans % mod;
}
int DistanceSum(int N, int *X, int *Y) {
map<pair<int, int>, int> nodes;
for(int i = 0; i < N; ++i){
nodes[{X[i], Y[i]}] = i;
}
vector<vector<int>> ed(N);
for(auto e:nodes){
int x = e.first.first;
int y = e.first.second;
if(nodes.count({x+1, y})){
ed[e.second].push_back(nodes[{x+1, y}]);
}
if(nodes.count({x-1, y})){
ed[e.second].push_back(nodes[{x-1, y}]);
}
if(nodes.count({x, y+1})){
ed[e.second].push_back(nodes[{x, y+1}]);
}
if(nodes.count({x, y-1})){
ed[e.second].push_back(nodes[{x, y-1}]);
}
}
ll ans = 0;
for(int i = 1; i < N; ++i){
ans += bfs(i, ed);
ans %= mod;
}
return ans;
}
