#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long
using namespace std;
const int modnum = 1000000000;
unordered_map<ll, int> gridmap;
unordered_map<int, int> blockmap;
ll total = 0;
ll ctoll(int a, int b) {
return a*1000000000 + b;
}
int dfs(vector<vector<int>> &graph, vector<int> &blocksize, int node, int parent, int n) {
pair<int,int> returnval;
int siz = blocksize[node];
for (int i : graph[node]) {
if (i != parent) {
siz += dfs(graph, blocksize, i, node, n);
}
}
total += siz * (n - siz);
total %= modnum;
//cout << total << endl;
return siz;
}
void solve(int n, int *x, int *y) {
gridmap.clear();
blockmap.clear();
//cout << endl;
for (int i=0;i<n;i++) {
gridmap[ctoll(x[i], y[i])] = i;
//cout << x[i] << ' ' << y[i] << endl;
}
//cout << endl;
int xnum = 0, top, bottom;
vector<int> blocksize(n);
for (int i=0;i<n;i++) {
if (blockmap.find(i) != blockmap.end()) continue;
blocksize[xnum] = 0;
top = y[i]; bottom = y[i];
while (gridmap.find(ctoll(x[i], top)) != gridmap.end()) {
blockmap[gridmap[ctoll(x[i], top)]] = xnum;
//cout << x[i] << ' ' << top << ' ' << gridmap[ctoll(x[i], top)] << endl;
top += 1; blocksize[xnum] += 1;
}
while (gridmap.find(ctoll(x[i], bottom)) != gridmap.end()) {
blockmap[gridmap[ctoll(x[i], bottom)]] = xnum;
//cout << x[i] << ' ' << bottom << ' ' << gridmap[ctoll(x[i], bottom)] << endl;
bottom -= 1; blocksize[xnum] += 1;
}
//cout << endl;
blocksize[xnum] -= 1;
xnum += 1;
}
/*
for (int i=0;i<n;i++) {
cout << i << " : " << blockmap[i] << endl;
}
cout << endl;
*/
vector<vector<int>> graph(n);
unordered_set<ll> edges;
for (int i=0;i<n;i++) {
if (gridmap.find(ctoll(x[i] - 1, y[i])) != gridmap.end()) {
if (edges.find(ctoll(blockmap[i], blockmap[gridmap[ctoll(x[i] - 1, y[i])]])) == edges.end()) {
edges.insert(ctoll(blockmap[i], blockmap[gridmap[ctoll(x[i] - 1, y[i])]]));
edges.insert(ctoll(blockmap[gridmap[ctoll(x[i] - 1, y[i])]], blockmap[i]));
graph[blockmap[i]].pb(blockmap[gridmap[ctoll(x[i] - 1, y[i])]]);
graph[blockmap[gridmap[ctoll(x[i] - 1, y[i])]]].pb(blockmap[i]);
//cout << i << ' ' << gridmap[ctoll(x[i] - 1, y[i])] << ' ' << blockmap[i] << ' ' << blockmap[ctoll(x[i] - 1, y[i])] << endl;
}
} else if (gridmap.find(ctoll(x[i] + 1, y[i])) != gridmap.end()) {
if (edges.find(ctoll(blockmap[i], blockmap[gridmap[ctoll(x[i] + 1, y[i])]])) == edges.end()) {
edges.insert(ctoll(blockmap[i], blockmap[gridmap[ctoll(x[i] + 1, y[i])]]));
edges.insert(ctoll(blockmap[gridmap[ctoll(x[i] + 1, y[i])]], blockmap[i]));
graph[blockmap[i]].pb(blockmap[gridmap[ctoll(x[i] + 1, y[i])]]);
graph[blockmap[gridmap[ctoll(x[i] + 1, y[i])]]].pb(blockmap[i]);
//cout << i << ' ' << gridmap[ctoll(x[i] + 1, y[i])] << ' ' << blockmap[i] << ' ' << blockmap[ctoll(x[i] + 1, y[i])] << endl;
}
}
}
//cout << endl;
/*
for (int i=0;i<xnum;i++) {
cout << i << " : ";
for (int j: graph[i]) {
cout << j << ' ';
}
cout << endl;
}
*/
dfs(graph, blocksize, 0, -1, n);
}
int DistanceSum(int n, int *x, int *y) {
int minx = INT32_MAX, miny = INT32_MAX;
for (int i=0;i<n;i++) {
minx = min(minx, x[i]);
miny = min(miny, y[i]);
}
for (int i=0;i<n;i++) {
x[i] -= minx;
y[i] -= miny;
}
solve(n, y, x);
solve(n, x, y);
return total;
}
