#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int *X, *Y, n;
ll ans;
map<pair<int, int>, int> st;
int dfs(int x, int y){
int ret = 1;
st[{x, y}] = 1;
for (int k=0;k<4;k++){
int nx = x + dx[k], ny = y + dy[k];
if (st[{nx, ny}]!=-1) continue;
int tmp = dfs(nx, ny);
if (k>=2) ans = (ans+(ll)tmp*(n-tmp))%MOD;
ret += tmp;
}
return ret;
}
int DistanceSum(int N, int *x, int *y) {
ans = 0;
n = N;
X = x, Y = y;
for (int i=0;i<n;i++) st[{x[i], y[i]}] = -1;
dfs(X[0], Y[0]);
for (int i=0;i<n;i++) st[{x[i], y[i]}] = -1;
dx[0] = 1, dx[1] = -1, dx[2] = 0, dx[3] = 0;
dy[0] = 0, dy[1] = 0, dy[2] = 1, dy[3] = -1;
dfs(X[0], Y[0]);
return ans;
}
