#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define oo 1000000000
#define ll long long
#define pb push_back
const int m = 1e9;
int distsum(int v, vector<vector<int>>& ed){
int n = ed.size();
vector<int> d(n);
vector<bool> visited(n);
queue<int> q;
q.push(v);
d[v] = 0;
visited[v] = true;
while (!q.empty()){
int cur = q.front();
q.pop();
for (auto x : ed[cur]){
if (visited[x]) continue;
visited[x] = true;
d[x] = d[cur] + 1;
q.push(x);
}
}
int res = 0;
for (int i = 0; i < n; ++i) {
res += d[i];
}
return res;
}
int DistanceSum(int n, int *x, int *y) {
int mn_x = oo, mn_y = oo;
for (int i = 0; i < n; ++i) {
mn_x = min(mn_x, x[i]);
mn_y = min(mn_y, y[i]);
}
int mx_x = 0, mx_y = 0;
for (int i = 0; i < n; ++i) {
x[i] = x[i] - mn_x + 1;
y[i] = y[i] - mn_y + 1;
mx_x = max(mx_x, x[i]);
mx_y = max(mx_y, y[i]);
}
vector<vector<int>> v(mx_x+1, vector<int>(mx_y + 1, -1));
for (int i = 0; i < n; ++i) {
v[x[i]][y[i]] = i;
}
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
vector<vector<int>> ed(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 4; ++j) {
int cur_x = x[i] + dx[j];
int cur_y = y[i] + dy[j];
if (v[cur_x][cur_y] != -1){
ed[i].pb(v[cur_x][cur_y]);
}
}
}
ll res = 0;
for (int i = 0; i < n; ++i) {
res += distsum(i, ed) * 1ll;
}
res /= 2ll;
return res % m;
}
