#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int mod = 1e9;
const int INF = 2147483646;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int n;
int res;
int sz[N];
int cnt[N];
int par[N];
int sum2[N];
int X[N], Y[N];
bool visit[N];
vector<int> G[N];
vector<int> G2[N];
vector<int> vec[N];
pair<int, int> L[N], R[N];
map< pair<int, int>, int > label;
int find(int u) {
return u == par[u] ? u : par[u] = find(par[u]);
}
void join(int u, int v) {
par[find(u)] = find(v);
}
struct Data {
int val, cnt, type;
bool operator < (const Data& rhs) const {
return val < rhs.val;
}
};
int calc(vector<Data> &vec) {
sort(vec.begin(), vec.end());
int ret = 0, sum;
sum = 0;
for (auto i : vec) sum2[i.type] = 0;
for (auto i : vec) {
int tmp = (sum + mod - sum2[i.type]) % mod;
ret = (ret + 1LL * tmp * i.val % mod * i.cnt) % mod;
sum = (sum + i.cnt) % mod;
sum2[i.type] = (sum2[i.type] + i.cnt) % mod;
}
reverse(vec.begin(), vec.end());
sum = 0;
for (auto i : vec) sum2[i.type] = 0;
for (auto i : vec) {
int tmp = (sum + mod - sum2[i.type]) % mod;
ret = (ret + mod - 1LL * tmp * i.val % mod * i.cnt % mod) % mod;
sum = (sum + i.cnt) % mod;
sum2[i.type] = (sum2[i.type] + i.cnt) % mod;
}
return ret;
}
void dfs(int u) {
sz[u] = vec[u].size();
visit[u] = 1;
vector<Data> vec2;
for (auto i : vec[u]) {
for (auto j : G[i]) {
int v = find(j);
if (visit[v]) continue;
// cout << u << ' ' << v << '\n';
L[v] = {INF, 0}, R[v] = {-INF, 0};
for (auto k : vec[v]) {
for (auto l : G[k]) {
if (find(l) != u) continue;
L[v] = min(L[v], {Y[k], k});
R[v] = max(R[v], {Y[k], k});
}
}
dfs(v), sz[u] += sz[v];
for (auto k : vec[v]) {
for (auto l : G[k]) {
if (find(l) != u) continue;
cnt[l] += cnt[k];
vec2.push_back({Y[k], cnt[k], v});
res = (res + 1LL * cnt[k] * (n - sz[v])) % mod;
// cout << k << ' ' << cnt[k] << ' ' << n - sz[v] << '\n';
}
}
}
}
for (auto i : vec[u]) {
vec2.push_back({Y[i], 1, i});
}
int tmp = calc(vec2);
res = (res + tmp) % mod;
// cout << "#at " << u << '\n';
// for (auto i : vec2) cout << i.first << ' ' << i.second << '\n';
// cout << tmp << '\n';
if (u == find(0)) return;
for (auto i : vec[u]) {
if (L[u].first <= Y[i] && Y[i] <= R[u].first) continue;
if (Y[i] < L[u].first) {
res = (res + 1LL * cnt[i] * (n - sz[u]) % mod * (L[u].first - Y[i])) % mod;
cnt[L[u].second] += cnt[i];
}
if (Y[i] > R[u].first) {
res = (res + 1LL * cnt[i] * (n - sz[u]) % mod * (Y[i] - R[u].first)) % mod;
cnt[R[u].second] += cnt[i];
}
}
}
int DistanceSum(int _n, int *_X, int *_Y) {
n = _n;
for (int i = 0; i < n; ++i) X[i] = _X[i], Y[i] = _Y[i];
for (int i = 0; i < n; ++i) {
label[{X[i], Y[i]}] = i;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 4; ++j) {
int x = X[i] + dx[j], y = Y[i] + dy[j];
if (label.count({x, y})) {
int id = label[{x, y}];
G[i].push_back(id);
}
}
}
for (int i = 0; i < n; ++i) par[i] = i;
for (int i = 0; i < n; ++i) {
for (auto j : G[i]) {
if (X[i] == X[j]) join(i, j);
}
}
for (int i = 0; i < n; ++i) {
cnt[i] = 1, vec[find(i)].push_back(i);
}
dfs(find(0));
return res;
}
