#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vb vector<bool>
#define pb push_back
#define ff(aa, bb, cc) for(ll aa = bb; aa < cc; aa++)
#define vl vector<ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define ed "\n"
#define all(aaa) aaa.begin(), aaa.end()
#define rall(aaa) aaa.rbegin(), aaa.rend()
ll MOD = 1000000000;
map<pll, ll> dist;
map<pll, bool> exists;
void flood(int x, int y, int sum){
//cout << x << " "<< y << ed;
if(!exists[{x, y}]){
return;
}
if(sum >= dist[{x, y}]){
//cout << "SUM MORE " << sum << " " << dist[{x, y}] << ed;
return;
}
dist[{x, y}] = sum;
if(exists[{x-1, y}]){
flood(x-1, y, sum+1);
}
if(exists[{x+1, y}]){
flood(x+1, y, sum+1);
}
if(exists[{x, y+1}]){
flood(x, y+1, sum+1);
}
if(exists[{x, y-1}]){
flood(x, y-1, sum+1);
}
}
int DistanceSum(int n, int *X, int *Y){
vector<pll> coords;
ff(i, 0, n){
coords.pb({X[i], Y[i]});
exists[{X[i], Y[i]}] = true;
}
ll c = 0;
ff(i, 0, n){
ll curx = coords[i].fi, cury = coords[i].se;
dist.clear();
for(auto &p : exists){
dist[{p.fi.fi, p.fi.se}] = INT_MAX;
}
flood(curx, cury, 0);
//cout << "===========" << ed;
ff(j, i+1, n){
//cout << dist[{X[j], Y[j]}] << ed;
c += dist[{X[j], Y[j]}] % MOD;
}
//cout << "===========" << ed;
c %= MOD;
}
return c%MOD;
}
/*
int main() {
ll n;
cin >> n;
int *x, *y;
x = (int*) malloc(n * sizeof(int));
y = (int*) malloc(n * sizeof(int));
ff(i, 0, n){
cin >> x[i] >> y[i];
}
ll res = DistanceSum(n, x, y);
cout << res << ed;
return 0;
}
*/
