#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 2010;
const ll INF = 1e18;
const ll MOD = 1e9;
int mark[MAXN][MAXN] , dist[MAXN][MAXN];
int dx[4] = {1 , -1 , 0 , 0} , dy[4] = {0 , 0 , 1 , -1};
ll ans;
void BFS(int x , int y){
queue<pii> Q;
dist[x][y] = 0; Q.push({x , y});
while(!Q.empty()){
pii A = Q.front(); Q.pop();
int x = A.first , y = A.second;
for(int i = 0 ; i < 4 ; i++){
int nx = x + dx[i] , ny = y + dy[i];
if(nx < 0 || ny < 0) continue;
if(dist[nx][ny] == MOD){
dist[nx][ny] = dist[x][y] + 1;
ans += dist[nx][ny];
Q.push({nx , ny});
}
}
}
}
ll DistanceSum(int N, int *X, int *Y) {
ll mnx = INF , mny = INF;
for(int i = 0 ; i < N ; i++){
mnx = min(mnx , (ll)X[i]);
mny = min(mny , (ll)Y[i]);
}
for(int i = 0 ; i < N ; i++){
X[i] -= mnx; Y[i] -= mny;
}
if(N > 2000){
sort(X , X + N);
sort(Y , Y + N);
ll sumx = 0 , sumy = 0;
for(int i = 0 ; i < N ; i++){
ans += 1ll * i * X[i] - sumx;
ans += 1ll * i * Y[i] - sumy;
sumx += X[i];
sumy += Y[i];
}
return ans % MOD;
}
for(int i = 0 ; i < N ; i++){
for(int j = 0 ; j < N ; j++) dist[X[j]][Y[j]] = MOD;
BFS(X[i] , Y[i]);
}
return ans / 2 % MOD;
}
