#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define X first
#define Y second
const int MAXN = 2e5 + 10;
const ll INF = 1e18;
const ll MOD = 1e9;
int n , par[MAXN] , sz[MAXN] , Sz[MAXN] , Par[MAXN];
ll ans;
vector<int> adj[MAXN];
vector<pii> vec;
int getInd(int x , int y){
int ind = lower_bound(vec.begin() , vec.end() , pii(x , y)) - vec.begin();
if(ind == n || vec[ind] != pii(x , y)) return -1;
return ind;
}
int Find(int v){
return (par[v] == -1 ? v : par[v] = Find(par[v]));
}
void Union(int v , int u){
v = Find(v); u = Find(u);
if(v == u) return;
if(sz[v] < sz[u]) swap(v , u);
par[u] = v;
sz[v] += sz[u];
}
void DFS(int v , int p = -1){
for(int u : adj[v]){
if(u == p) continue;
DFS(u , v);
Sz[v] += Sz[u];
}
ans += Sz[v] * (n - Sz[v]);
}
void solve(){
fill(par , par + MAXN , -1);
fill(sz , sz + MAXN , 1);
sort(vec.begin() , vec.end());
for(int i = 0 ; i < n ; i++){
adj[i].clear();
int x = vec[i].X , y = vec[i].Y;
int ind = getInd(x , y - 1);
if(ind == -1) continue;
Union(i , ind);
}
for(int i = 0 ; i < MAXN ; i++) Sz[i] = sz[i] , Par[i] = Find(i);
for(int i = 0 ; i < n ; i++){
int x = vec[i].X , y = vec[i].Y;
int ind = getInd(x - 1 , y);
if(ind == -1) continue;
if(Find(ind) == Find(i)) continue;
adj[Par[ind]].push_back(Par[i]);
adj[Par[i]].push_back(Par[ind]);
Union(i , ind);
}
DFS(Find(0));
}
ll DistanceSum(int N, int *X, int *Y) {
n = N;
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;
}
for(int i = 0 ; i < N ; i++) vec.push_back({X[i] , Y[i]});
solve(); vec = {};
for(int i = 0 ; i < N ; i++) vec.push_back({Y[i] , X[i]});
solve();
return ans % MOD;
}
