#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define all(x) x.begin(), x.end()
#define kill(x) return cout << x << endl, 0
#define endl '\n'
constexpr ll pw(ll a, ll b, ll mod) {
return (!b ? 1 :
b & 1 ? a * pw(a * a % mod, b / 2, mod) % mod :
pw(a * a % mod, b / 2, mod));
}
constexpr int N = 1e5 + 10;
constexpr int MOD = 1e9;
int n, par[N], sz[N];
vector<int> A, B;
vector<int> row[N], col[N];
vector<int> adj[N];
ll ans;
void add_edge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
void DFS(int u, int p) {
for (int v : adj[u]) if (v != p) {
DFS(v, u);
ans += (ll) sz[v] * (n - sz[v]);
sz[u] += sz[v];
}
}
int DistanceSum(int n_, int *X, int *Y) {
n = n_;
for (int i = 0; i < n; i++) {
A.push_back(X[i]);
B.push_back(Y[i]);
}
sort(all(A)); A.erase(unique(all(A)), A.end());
sort(all(B)); B.erase(unique(all(B)), B.end());
for (int i = 0; i < n; i++) {
X[i] = lower_bound(all(A), X[i]) - A.begin();
Y[i] = lower_bound(all(B), Y[i]) - B.begin();
row[X[i]].push_back(i);
col[Y[i]].push_back(i);
}
for (int i = 0; i < A.size(); i++) {
sort(all(row[i]), [&Y] (int i, int j) { return Y[i] < Y[j]; });
}
for (int i = 0; i < B.size(); i++) {
sort(all(col[i]), [&X] (int i, int j) { return X[i] < X[j]; });
}
// =========== X Axis ============
iota(par, par + n, 0);
fill(sz, sz + n, 1);
for (int i = 0; i < A.size(); i++) {
for (int j = 0; j < row[i].size(); j++) {
if (j && Y[row[i][j - 1]] + 1 == Y[row[i][j]]) {
par[row[i][j]] = par[row[i][j - 1]];
sz[par[row[i][j]]]++;
}
}
}
for (int i = 1; i < A.size(); i++) {
int ptr = 0;
for (int j = 0; j < row[i].size(); j++) {
while (ptr < row[i - 1].size() && Y[row[i - 1][ptr]] < Y[row[i][j]])
ptr++;
if (ptr == row[i - 1].size())
break;
if (Y[row[i - 1][ptr]] != Y[row[i][j]])
continue;
if (j == 0 || par[row[i][j - 1]] != par[row[i][j]] || ptr == 0 || par[row[i - 1][ptr - 1]] != par[row[i - 1][ptr]]) {
add_edge(par[row[i][j]], par[row[i - 1][ptr]]);
}
}
}
DFS(par[0], -1);
// =========== Y Axis ============
iota(par, par + n, 0);
fill(sz, sz + n, 1);
for (int i = 0; i < n; i++)
adj[i].clear();
for (int i = 0; i < B.size(); i++) {
for (int j = 0; j < col[i].size(); j++) {
if (j && X[col[i][j - 1]] + 1 == X[col[i][j]]) {
par[col[i][j]] = par[col[i][j - 1]];
sz[par[col[i][j]]]++;
}
}
}
for (int i = 1; i < B.size(); i++) {
int ptr = 0;
for (int j = 0; j < col[i].size(); j++) {
while (ptr < col[i - 1].size() && X[col[i - 1][ptr]] < X[col[i][j]])
ptr++;
if (ptr == col[i - 1].size())
break;
if (X[col[i - 1][ptr]] != X[col[i][j]])
continue;
if (j == 0 || par[col[i][j - 1]] != par[col[i][j]] || ptr == 0 || par[col[i - 1][ptr - 1]] != par[col[i - 1][ptr]]) {
add_edge(par[col[i][j]], par[col[i - 1][ptr]]);
}
}
}
DFS(par[0], -1);
return ans % MOD;
}
