#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int m = 1000000000;
unordered_set<ll> s_orig;
ll hashval(int x, int y){
return x*(1LL<<31)+y;
}
ll bfs(int startx, int starty){
unordered_set<ll> unvisited = s_orig;
unvisited.erase(hashval(startx,starty));
queue<pair<pair<int,int>,ll>> q;
q.push({{startx,starty},0});
ll total = 0;
while (q.size()>0){
auto f = q.front();
q.pop();
int x = f.first.first;
int y = f.first.second;
int dist = f.second;
for (int i = 0; i<4; i++){
int nx = x+dx[i];
int ny = y+dy[i];
auto f = unvisited.find(hashval(nx,ny));
if (f!=unvisited.end()){
unvisited.erase(f);
total+=dist+1;
q.push({{nx,ny},dist+1});
}
}
}
return total;
}
int subtask2(int n, int *x, int *y){
for (int i = 0; i<n; i++){
s_orig.insert(hashval(x[i],y[i]));
}
ll tot = 0;
for (int i = 0; i<n; i++){
tot += bfs(x[i],y[i]);
}
tot/=2;
return tot%m;
}
int *xv, *yv;
bool cmpltr(int i, int j){
if (yv[i]==yv[j]){
return xv[i]<xv[j];
} else {
return yv[i]<yv[j];
}
}
bool cmprtl(int i, int j){
if (yv[i]==yv[j]){
return xv[i]>xv[j];
} else {
return yv[i]<yv[j];
}
}
int subtask3(int n, int *x, int *y){
xv=x;yv=y;
vector<int> order(n);
for (int i = 0; i<n; i++){
order[i]=i;
}
ll tot = 0;
//ltr
sort(order.begin(),order.end(),cmpltr);
unordered_map<ll,ll> nltr;
for (int i = 0; i<n; i++){
int ind = order[i];
ll cur = hashval(x[ind],y[ind]);
ll curl = hashval(x[ind]-1,y[ind]);
ll curu = hashval(x[ind],y[ind]-1);
ll curlu = hashval(x[ind]-1,y[ind]-1);
nltr[cur]=1;
if (nltr.find(curl)!=nltr.end()){
nltr[cur]+=nltr[curl];
}
if (nltr.find(curu)!=nltr.end()){
nltr[cur]+=nltr[curu];
}
if (nltr.find(curlu)!=nltr.end()){
nltr[cur]-=nltr[curlu];
}
}
unordered_map<ll,ll> cntltr;
for (int i = 0; i<n; i++){
int ind = order[i];
ll cur = hashval(x[ind],y[ind]);
ll curl = hashval(x[ind]-1,y[ind]);
ll curu = hashval(x[ind],y[ind]-1);
ll curlu = hashval(x[ind]-1,y[ind]-1);
cntltr[cur]=0;
if (nltr.find(curl)!=nltr.end()){
cntltr[cur]+=nltr[curl]*cntltr[curl];
}
if (nltr.find(curu)!=nltr.end()){
cntltr[cur]+=nltr[curu]*cntltr[curu];
}
if (nltr.find(curlu)!=nltr.end()){
cntltr[cur]-=nltr[curlu]*cntltr[curlu];
}
tot+=cntltr[cur];
}
sort(order.begin(),order.end(),cmprtl);
unordered_map<ll,ll> nrtl;
for (int i = 0; i<n; i++){
int ind = order[i];
ll cur = hashval(x[ind],y[ind]);
ll curl = hashval(x[ind]-1,y[ind]);
ll curu = hashval(x[ind],y[ind]-1);
ll curlu = hashval(x[ind]-1,y[ind]-1);
nrtl[cur]=1;
if (nrtl.find(curl)!=nrtl.end()){
nrtl[cur]+=nrtl[curl];
}
if (nrtl.find(curu)!=nrtl.end()){
nrtl[cur]+=nrtl[curu];
}
if (nrtl.find(curlu)!=nrtl.end()){
nrtl[cur]-=nrtl[curlu];
}
}
unordered_map<ll,ll> cntrtl;
for (int i = 0; i<n; i++){
int ind = order[i];
ll cur = hashval(x[ind],y[ind]);
ll curl = hashval(x[ind]-1,y[ind]);
ll curu = hashval(x[ind],y[ind]-1);
ll curlu = hashval(x[ind]-1,y[ind]-1);
cntrtl[cur]=0;
if (nrtl.find(curl)!=nrtl.end()){
cntrtl[cur]+=nrtl[curl]*cntrtl[curl];
}
if (nrtl.find(curu)!=nrtl.end()){
cntrtl[cur]+=nrtl[curu]*cntrtl[curu];
}
if (nrtl.find(curlu)!=nrtl.end()){
cntrtl[cur]-=nrtl[curlu]*cntrtl[curlu];
}
tot+=cntrtl[cur];
}
//now take away double counting
//horizontal
unordered_map<int,pair<int,int>> yx;
unordered_map<int,pair<int,int>> xy;
for (int i = 0; i<n; i++){
yx[y[i]].first=min(yx[y[i]].first,-x[i]);
yx[y[i]].second=max(yx[y[i]].first,x[i]);
xy[x[i]].first=min(xy[x[i]].first,-y[i]);
xy[x[i]].second=max(xy[x[i]].first,y[i]);
}
for (auto p : yx){
int minv = -p.second.first;
int maxv = p.second.second;
int len = maxv-minv+1;
ll tt = len*(len-1)/2;
tot-=tt;
}
for (auto p : xy){
int minv = -p.second.first;
int maxv = p.second.second;
int len = maxv-minv+1;
ll tt = len*(len-1)/2;
tot-=tt;
}
return tot;
}
int DistanceSum(int n, int *x, int *y) {
if (n<=2000){
return subtask2(n,x,y);
} else {
return subtask3(n,x,y);
}
}
