#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#pragma GCC optimize ("O3")
#pragma GCC optimize ("O2")
#define F first
#define S second
//#define endl '\n'
//#define int long long
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
const int MOD = 1e9;
using namespace std;
int dist[4000007];
vt<pii> cell;
int bfs(pii start, int i)
{
for(pii x : cell) dist[x.F] = INT_MAX;
queue<pii> q;
q.push(start);
dist[start.F * 2000 + start.S] = 0;
while(!q.empty())
{
pii v = q.front();
q.pop();
int d, i1, i2, i3, i4;
d = dist[v.F * 2000 + v.S];
i1 = (v.F + 1) * 2000 + v.S, i2 = (v.F - 1) * 2000 + v.S;
i3 = v.F * 2000 + v.S + 1, i4 = v.F * 2000 + v.S - 1;
if (dist[i1] > d + 1)
q.push({v.F + 1, v.S}), dist[i1] = d + 1;
if (dist[i2] > d + 1)
q.push({v.F - 1, v.S}), dist[i2] = d + 1;
if (dist[i3] > d + 1)
q.push({v.F, v.S + 1}), dist[i3] = d + 1;
if (dist[i4] > d + 1)
q.push({v.F, v.S - 1}), dist[i4] = d + 1;
}
int ans = 0;
for(pii x : cell)
if (x.S > i) ans = (1ll * ans + dist[x.F]) % MOD;
return ans;
}
int subtask12(int N, int* X, int* Y)
{
int mn_X = INT_MAX, mn_Y = INT_MAX;
for(int i = 0; i < N; i++)
mn_X = min(mn_X, *(X + i) - 1), mn_Y = min(mn_Y, *(Y + i) - 1);
for(int i = 0; i < N; i++)
cell.pb({(*(X + i) - mn_X) * 2000 + (*(Y + i) - mn_Y), i});
int ans = 0;
for(int i = 0; i < N; i++)
ans = (1ll * ans + bfs({(*(X + i) - mn_X), (*(Y + i) - mn_Y)}, i)) % MOD;
return ans;
}
int DistanceSum(int N, int* X, int* Y)
{
if (N <= 2000) return subtask12(N, X, Y);
}
/*
11
2 5
2 6
3 3
3 6
4 3
4 4
4 5
4 6
5 3
5 4
5 6
20
3 5
4 6
2 5
3 4
6 5
1 6
2 7
3 1
2 6
1 5
5 5
5 4
4 7
4 2
3 2
3 3
4 4
4 3
4 5
5 2
*/
