#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int mod = 1e9;
const int nmax = 1e5;
i64 sum;
int n;
int sz[nmax + 1], comp[nmax + 1];
bool viz[nmax + 1];
vector<int> g[nmax + 1];
map<pair<int, int>, int> mp;
void dfs (int nod, pair<int, int> pos, int ind) { // componentele sunt secventele consec pe ac coloana
if (viz[nod] == 1)
return ;
++ sz[ind];
viz[nod] = 1;
comp[nod] = ind;
-- pos.first;
if (mp.find(pos) != mp.end()) {
dfs(mp[pos], pos, ind);
}
pos.first += 2;
if (mp.find(pos) != mp.end()) {
dfs(mp[pos], pos, ind);
}
}
void calc (int nod, int t) {
for (auto i : g[nod]) {
if (i != t) {
calc(i, nod);
sz[nod] += sz[i];
}
}
sum = (sum + 1LL * sz[nod] * (n - sz[nod])) % mod;
}
int solve (int N, int *X, int *Y) {
for (int i = 0; i < N; ++ i)
mp[{X[i], Y[i]}] = i;
int nrc = 0;
for (int i = 0; i < N; ++ i) {
if (viz[i] == 0) {
dfs(i, {X[i], Y[i]}, ++ nrc);
}
}
n = N;
for (int i = 0; i < N; ++ i) {
int y = Y[i] + 1;
if (mp.find({X[i], y}) != mp.end()) {
int u = comp[mp[{X[i], y}]];
g[comp[i]].push_back(u);
g[u].push_back(comp[i]);
}
}
for (int i = 1; i <= nrc; ++ i) {
sort(g[i].begin(), g[i].end());
g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
}
sum = 0;
calc(1, 0);
memset(sz, 0, sizeof(sz));
memset(viz, 0, sizeof(viz));
mp.clear();
for (int i = 1; i <= nrc; ++ i) {
g[i].clear();
}
return sum;
}
int DistanceSum(int N, int *X, int *Y) {
int ans = solve(N, X, Y) + solve(N, Y, X);
return ans % mod;
}
