#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 100'010;
vector<int> A[N];
int sub_sz[N];
int weight_node[N];
int n;
int dfs1(int v, int p)
{
sub_sz[v] = weight_node[v];
for (int u : A[v]) {
if (u != p)
sub_sz[v] += dfs1(u, v);
}
return sub_sz[v];
}
ll dfs2(int v, int p)
{
ll ans = 0;
for (int u : A[v]) {
if (u == p)
continue;
ans += (ll)sub_sz[u] * (n - sub_sz[u]);
ans += dfs2(u, v);
}
return ans;
}
void make_tree(set<pii> nodes)
{
Loop (i,0,N)
A[i].clear();
map<pii, int> col;
int cnt = 0;
for (pii v : nodes) {
if (col.count(v))
continue;
weight_node[cnt] = 0;
for (pii u = v; nodes.count(u); u.second++) {
col[u] = cnt;
weight_node[cnt]++;
pii w = u; w.first -= 1;
if (nodes.count(w)) {
int c = col[w];
if (!A[cnt].size() || A[cnt].back() != c) {
A[c].push_back(cnt);
A[cnt].push_back(c);
}
}
}
++cnt;
}
//for (pii v : nodes) {
// printf("col[%d, %d] = %d: ", v.first, v.second, col[v]);
// for (int u : A[col[v]])
// printf("%d ", u);
// printf("\n");
//}
}
int DistanceSum(int N, int *X, int *Y)
{
set<pii> s1, s2;
Loop (i,0,N) {
s1.insert({X[i], Y[i]});
s2.insert({Y[i], X[i]});
}
::n = N;
ll ans = 0;
make_tree(s1);
dfs1(0, -1);
ans += dfs2(0, -1);
make_tree(s2);
dfs1(0, -1);
ans += dfs2(0, -1);
ans %= 1'000'000'000;
return ans;
}
