#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000
#define MOD 1000000000
using namespace std;
map <pair<int,int>,int> a;
set <int> L[DIM],L2[DIM];
deque <int> c;
pair <int,int> v[DIM];
int what_comp[DIM],what_comp2[DIM],Size[DIM],Size2[DIM],dist[DIM],viz[DIM];
int nr_nodes, nr_nodes2;
int di[] = {-1,1,0,0};
int dj[] = {0,0,-1,1};
int bfs (int start){
int i;
for (i=1;i<=nr_nodes;i++)
dist[i] = INF;
c.clear();
c.push_back(start);
dist[start] = 0;
int sol = 0;
while (!c.empty()){
int nod = c.front();
c.pop_front();
for (auto vecin : L[nod]){
if (dist[vecin] == INF){
dist[vecin] = 1 + dist[nod];
sol += 1LL * dist[vecin] * Size[vecin] % MOD;
c.push_back(vecin);
}}}
return sol;
}
int bfs2 (int start){
int i;
for (i=1;i<=nr_nodes2;i++)
dist[i] = INF;
c.clear();
c.push_back(start);
dist[start] = 0;
int sol = 0;
while (!c.empty()){
int nod = c.front();
c.pop_front();
for (auto vecin : L2[nod]){
if (dist[vecin] == INF){
dist[vecin] = 1 + dist[nod];
sol += 1LL * dist[vecin] * Size2[vecin] % MOD;
c.push_back(vecin);
}}}
return sol;
}
int DistanceSum (int n, int *X, int *Y){
int i;
long long sol = 0;
for (i=1;i<=n;i++){
v[i] = make_pair (X[i-1],Y[i-1]);
a[v[i]] = i;
}
/// grupez celulele pe orizontala si pe verticala si o sa am 2 arbori
/// orizontala
for (i=1;i<=n;i++){
if (!viz[i]){
viz[i] = 1;
what_comp[i] = ++nr_nodes;
int x = v[i].first, y = v[i].second, cnt = 1;
while (a[make_pair(x,y+1)]){
y++, cnt++;
int idx = a[make_pair(x,y)];
viz[idx] = 1;
what_comp[idx] = nr_nodes;
}
y = v[i].second;
while (a[make_pair(x,y-1)]){
y--, cnt++;
int idx = a[make_pair(x,y)];
viz[idx] = 1;
what_comp[idx] = nr_nodes;
}
Size[nr_nodes] = cnt;
}
}
/// construiesc primul arbore
for (i=1;i<=n;i++){
int ic = v[i].first, jc = v[i].second;
int x = what_comp[i];
for (int dir=0;dir<=3;dir++){
int iv = ic + di[dir];
int jv = jc + dj[dir];
int idx = a[make_pair(iv,jv)];
if (!idx)
continue;
int y = what_comp[idx];
if (x != y){
L[x].insert(y);
L[y].insert(x);
}}}
/// verticala
memset (viz,0,sizeof viz);
for (i=1;i<=n;i++){
if (!viz[i]){
viz[i] = 1;
what_comp2[i] = ++nr_nodes2;
int x = v[i].first, y = v[i].second, cnt = 1;
while (a[make_pair(x-1,y)]){
x--, cnt++;
int idx = a[make_pair(x,y)];
viz[idx] = 1;
what_comp2[idx] = nr_nodes2;
}
x = v[i].first;
while (a[make_pair(x+1,y)]){
x++, cnt++;
int idx = a[make_pair(x,y)];
viz[idx] = 1;
what_comp2[idx] = nr_nodes2;
}
Size2[nr_nodes2] = cnt;
}
}
for (i=1;i<=n;i++){
int ic = v[i].first, jc = v[i].second;
int x = what_comp2[i];
for (int dir=0;dir<=3;dir++){
int iv = ic + di[dir];
int jv = jc + dj[dir];
int idx = a[make_pair(iv,jv)];
if (!idx)
continue;
int y = what_comp2[idx];
if (x != y){
L2[x].insert(y);
L2[y].insert(x);
}}}
/// stiu ca o sa iau tle
for (i=1;i<=nr_nodes;i++)
sol = sol + 1LL * Size[i] * bfs(i);
for (i=1;i<=nr_nodes2;i++)
sol = sol + 1LL * Size2[i] * bfs2(i);
return (sol / 2) % MOD;
}
