#include <iostream>
#include <map>
#include <set>
#include <utility>
#include <vector>
long long MOD = 1e9;
int n;
int ansFor(std::set<std::pair<int, int>> &coords) {
std::map<std::pair<int, int>, int> colors;
int cur = 0;
std::vector<std::vector<int>> adj;
std::vector<int> weight;
for (auto [x, y] : coords) {
// std::cout << x << ' ' << y << '\n';
// std::cout << "(" << cur << ")\n";
if (cur >= adj.size()) adj.emplace_back(), weight.emplace_back();
if (coords.count(std::make_pair(x - 1, y)) && !(coords.count(std::make_pair(x - 1, y - 1)) && coords.count(std::make_pair(x, y - 1)))) {
adj[cur].push_back(colors[std::make_pair(x - 1, y)]);
adj[colors[std::make_pair(x - 1, y)]].push_back(cur);
}
colors[std::make_pair(x, y)] = cur;
++weight[cur];
if (!coords.count(std::make_pair(x, y + 1))) ++cur;
}
// for (int i = 0; i < adj.size(); ++i) {
// std::cout << i << ':';
// for (int j : adj[i]) {
// std::cout << ' ' << j;
// }
// std::cout << '\n';
// }
long long ans = 0;
auto dfs = [&](int node, int p, auto dfs) -> long long {
long long myweight = weight[node];
for (int to : adj[node]) {
if (to == p) continue;
myweight += dfs(to, node, dfs);
}
ans += (myweight) * (n - myweight);
ans %= MOD;
return myweight;
};
dfs(0, -1, dfs);
return ans;
}
int DistanceSum(int N, int *X, int *Y) {
n = N;
std::set<std::pair<int, int>> normalcoords;
for (int i = 0; i < N; ++i) {
normalcoords.emplace(X[i], Y[i]);
}
long long ans = 0;
ans += ansFor(normalcoords);
ans %= MOD;
std::set<std::pair<int, int>> flippedcoords;
for (int i = 0; i < N; ++i) {
flippedcoords.emplace(Y[i], X[i]);
}
ans += ansFor(flippedcoords);
ans %= MOD;
return ans;
}
