#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int maxn = 1e5 + 5;
const int mod = 1e9;
vector<int> graph[maxn];
vector<ll> sub(maxn), sz(maxn);
void dfs(int u, int p) {
sub[u] = sz[u];
for(int &v : graph[u]) {
if(v == p) continue;
dfs(v, u);
// cout << u << " -> " << v << '\n';
sub[u] += sub[v];
}
}
ll solve(vector<pii> v, int N, int *X, int *Y) {
for(int i=0; i<maxn; i++) {
graph[i].clear();
sub[i] = sz[i] = 0;
}
int mn = 1e9, mx = 0;
for(int i=0; i<N; i++) {
mn = min(mn, v[i].first);
mx = max(mx, v[i].first);
}
int curr = 1, total = 0;
int p = 0, start = 0;
vector<array<int, 3> > ivals;
for(int i=mn; i<=mx; i++) {
// cout << i << ": " << ivals.size() << '\n';
start = p;
int last = v[p].second-1;
vector<array<int, 3> > nvals;
int ptr = 0;
while(p < N && v[p].first == i) {
if(v[p].second - last > 1) {
for(auto &[L, r, id] : ivals) {
if(min(r, v[p-1].second) - max(L, v[start].second) >= 0) {
graph[id].push_back(curr);
graph[curr].push_back(id);
}
}
nvals.push_back({ v[start].second, v[p-1].second, curr });
start = p;
curr++;
}
sz[curr]++;
last = v[p].second;
p++;
}
if(start < p) {
for(auto &[L, r, id] : ivals) {
if(min(r, v[p-1].second) - max(L, v[start].second) >= 0) {
graph[id].push_back(curr);
graph[curr].push_back(id);
}
}
nvals.push_back({ v[start].second, v[p-1].second, curr });
start = p;
}
curr++;
ivals = nvals;
}
curr--;
dfs(1, 1);
ll ans = 0;
for(int i=2; i<=curr; i++) ans = (ans + sub[i] % mod * ((ll)N - sub[i]) % mod) % mod;
return ans;
}
int DistanceSum(int N, int *X, int *Y) {
if(N <= 2000) {
vector<int> graph[N];
for(int i=0; i<N; i++) {
for(int j=i+1; j<N; j++) {
if(abs(X[i] - X[j]) + abs(Y[i] - Y[j]) == 1) {
graph[i].push_back(j);
graph[j].push_back(i);
}
}
}
int ans = 0;
for(int i=0; i<N; i++) {
queue<int> q;
vector<bool> vis(N);
vector<int> dist(N);
vis[i] = 1; q.push(i);
while(!q.empty()) {
int u = q.front(); q.pop();
for(int &v : graph[u]) {
if(vis[v]) continue;
vis[v] = 1;
dist[v] = dist[u] + 1;
q.push(v);
}
}
for(int j=i+1; j<N; j++) ans += dist[j];
}
return ans;
}
vector<pii> v;
for(int i=0; i<N; i++) v.push_back({ X[i], Y[i] });
sort(v.begin(), v.end());
ll ans = solve(v, N, X, Y);
for(int i=0; i<N; i++) swap(v[i].first, v[i].second);
sort(v.begin(), v.end());
return (ans + solve(v, N, X, Y)) % mod;
}
