#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 20;
const long long mod = 1e9;
vector<int> adj[maxN];
pair<int, int> ranges[maxN];
int sum[maxN];
pair<int, int> pos[maxN];
map<pair<int, int>, int> comp_id;
set<pair<int, int>> edges;
int comp_cnt;
bool cmp(pair<int, int> p1, pair<int, int> p2) {
return p1.second < p2.second;
}
int get_id(int x, int y) {
auto it = comp_id.find(make_pair(x, y));
if (it == comp_id.end()) {
return -1;
}
else {
return it->second;
}
}
long long res = 0;
void dfs(int u, int p) {
for (auto v: adj[u]) {
if (v != p) {
dfs(v, u);
sum[u] += sum[v];
}
}
}
int DistanceSum(int N, int *X, int *Y) {
for (int i = 1; i <= N; i++) {
pos[i].first = X[i - 1];
pos[i].second = Y[i - 1];
}
res = 0;
for (int iter = 0; iter < 2; iter++) {
comp_id.clear();
edges.clear();
for (int i = 1; i <= N; i++) {
comp_id[make_pair(pos[i].first, pos[i].second)] = -2;
adj[i].clear();
}
sort(pos + 1, pos + N + 1, cmp);
comp_cnt = 0;
for (int i = 1; i <= N; i++) {
int x = pos[i].first;
int y = pos[i].second;
int id = get_id(x, y - 1);
if (id == -1) {
id = ++comp_cnt;
ranges[id].first = y;
}
comp_id[make_pair(x, y)] = id;
if (get_id(x, y + 1) == -1) {
ranges[id].second = y;
sum[id] = ranges[id].second - ranges[id].first + 1;
}
}
for (int i = 1; i <= N; i++) {
int x = pos[i].first;
int y = pos[i].second;
int u = get_id(x, y);
int v = get_id(x - 1, y);
if (u != -1 && v != -1) {
edges.emplace(u, v);
edges.emplace(v, u);
}
}
for (auto e: edges) {
adj[e.first].push_back(e.second);
}
dfs(1, -1);
for (int i = 1; i <= comp_cnt; i++) {
res += 1LL * sum[i] * (sum[1] - sum[i]);
}
for (int i = 1; i <= N; i++) {
swap(pos[i].first, pos[i].second);
}
}
res %= mod;
return res;
}
