#include <bits/stdc++.h>
using namespace std;
const int N = 100000, MD = 1000000000;
int eo[N], *ej[N], vis[N], sz[N], cc[N], vis_[N];
map<pair<int, int>, int> aa, bb;
long long dp[N], ans;
int add(int x, int y) { return x + y > MD ? x + y - MD : x + y; }
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], 2 * o * sizeof *ej[i]);
ej[i][o] = j;
}
void dfs1(int i, int d, int st) {
int o;
dp[st] += d * cc[i], sz[i] = cc[i], vis[i] = 1;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (!vis[j]) {
dfs1(j, d + 1, st);
sz[i] += sz[j];
}
}
}
void dfs2(int i, int p, int st) {
int o;
ans += dp[i] * cc[i], vis_[i] = 1;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (vis_[j] == 1)
continue;
dp[j] = dp[i];
dp[j] -= sz[j];
dp[j] += sz[st] - sz[j];
dfs2(j, i, st);
}
}
int solve(int n, int *x, int *y) {
int i, _, x_;
aa.clear(), bb.clear();
for (i = 0; i < n; i++)
bb[{x[i], y[i]}] = 1;
for (i = 0, _ = 0; i < n; i++) {
if (aa[{x[i], y[i]}] != 0)
continue;
aa[{x[i], y[i]}] = ++_;
x_ = x[i];
while (bb[{--x_, y[i]}] == 1)
aa[{x_, y[i]}] = _;
x_ = x[i];
while (bb[{++x_, y[i]}] == 1)
aa[{x_, y[i]}] = _;
}
memset(cc, 0, (_ + 1) * sizeof *cc);
for (i = 0; i < n; i++)
cc[aa[{x[i], y[i]}]]++;
for (i = 0; i < n; i++)
eo[i] = 0, ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (i = 0; i < n; i++)
if (aa[{x[i], y[i] + 1}] != 0)
append(aa[{x[i], y[i]}], aa[{x[i], y[i] + 1}]), append(aa[{x[i], y[i] + 1}], aa[{x[i], y[i]}]);
ans = 0;
for (i = 1; i <= _; i++)
if (!vis[i]) {
dp[i] = 0;
dfs1(i, 0, i);
dfs2(i, i, i);
}
for (i = 1; i <= _; i++)
vis[i] = vis_[i] = 0;
return (ans / 2) % MD;
}
int DistanceSum(int n, int *x, int *y) {
return add(solve(n, x, y), solve(n, y, x));
}
