#include <bits/stdc++.h>
//#include "grader.h"
using namespace std;
#define S second
#define F first
#define LL long long
const int N1 = 4e5+10;
const LL MOD = 1e9;
const LL LINF = 1e18;
const LL INF = 1e9;
int x[] = {1,-1,0,0};
int y[] = {0,0,1,-1};
vector<int>adj[N1];
map<pair<int,int>,int>mp,vis1;
int cnt = 1,n;
int dis[N1],vis[N1];
void dfs(int i,int j){
if(vis1[{i,j}])return ;
vis1[{i,j}] = 1;
mp[{i,j}] = cnt++;
for(int k=0;k<4;k++){
int i1 = i+x[k],j1 = j+y[k];
if(mp[{i1,j1}])dfs(i1,j1),adj[mp[{i,j}]].push_back(mp[{i1,j1}]);
}
}
LL dijikstra(int st){
LL ret = 0;
for(int i=1;i<=n;i++)
dis[i] = INF,vis[i] = 0;
dis[st] = 0;
priority_queue<pair<int,int>>que;
que.push({0,st});
while(!que.empty()){
int u = que.top().S;
que.pop();
if(vis[u])continue;
vis[u] = 1;
if(u>=st)
ret = (ret+dis[u])%MOD;
for(auto x:adj[u])
dis[x] = min(dis[x],dis[u]+1),que.push({-dis[x],x});
}
return ret;
}
int DistanceSum(int N, int *X, int *Y) {
n = N;
for(int i=0;i<n;i++)
mp[{X[i],Y[i]}] = 1;
dfs(X[0],Y[0]);
LL ret = 0;
for(int i=1;i<=n;i++)
ret = (ret+dijikstra(i))%MOD;
return ret;
}
