#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<int> g[100000];
int weight[100000];
ll result = 0;
ll dfs(int u, int p = -1)
{
ll sz = weight[u];
for (int v : g[u])
if (v != p)
sz += dfs(v, u);
result = (result + sz * (n - sz)) % 1000000000;
return sz;
}
vector<pair<int, int>> cells;
void solve(int N, int *X, int *Y)
{
n = N;
cells.resize(0);
for (int i = 0; i < N; i++)
cells.push_back({X[i], Y[i]});
sort(cells.begin(), cells.end());
int num_blocks = 0;
map<pair<int, int>, int> block;
for (int i = 0, j; i < N; i = j + 1) {
block[cells[i]] = num_blocks;
j = i;
while (j+1 < N && cells[j+1].first == cells[i].first && cells[j+1].second == cells[j].second + 1) {
block[cells[++j]] = num_blocks;
}
weight[num_blocks] = j - i + 1;
num_blocks++;
}
set<pair<int, int>> edges;
for (int i = 0; i < N; i++) {
pair<int, int> other_cell = {cells[i].first - 1, cells[i].second};
if (block.find(other_cell) != block.end()) {
edges.insert(make_pair(block[cells[i]], block[other_cell]));
}
}
for (auto &[u, v] : edges) {
g[u].push_back(v);
g[v].push_back(u);
}
dfs(0);
}
int DistanceSum(int N, int *X, int *Y)
{
result = 0;
solve(N, X, Y);
solve(N, Y, X);
return result;
}
