#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <tuple>
#include <vector>
using u32 = uint32_t;
using u64 = uint64_t;
using pii = std::pair<u32, u32>;
using tiii = std::tuple<u32, u32, u32>;
constexpr u32 mod = 1e9;
static int foo(int n, int x[], int y[]) {
std::vector<pii> p(n);
for (int i = 0; i < n; ++i) p[i] = {x[i], y[i]};
sort(p.begin(), p.end());
std::vector<char> f(n, false);
std::function<tiii(u32)> const rec = [&](u32 i) -> tiii {
// std::cerr << "OPEN\t" << p[i].first << ' ' << p[i].second << '\n';
u32 j = i + 1;
while (i > 0 && p[i - 1].first == p[i].first && p[i - 1].second + 1 == p[i].second) --i;
while (j < n && p[j - 1].first == p[j].first && p[j - 1].second + 1 == p[j].second) ++j;
for (u32 k = i; k < j; ++k) {
assert(f[k] == false);
f[k] = true;
}
std::vector<tiii> v;
for (auto it =
lower_bound(p.begin(), p.end(), pii{p[i].first - 1, p[i].second}) - p.begin();
it < n && p[it] <= pii{p[j - 1].first - 1, p[j - 1].second}; ++it) {
if (f[it]) continue;
v.push_back(rec(it));
}
for (auto it =
lower_bound(p.begin(), p.end(), pii{p[i].first + 1, p[i].second}) - p.begin();
it < n && p[it] <= pii{p[j - 1].first + 1, p[j - 1].second}; ++it) {
if (f[it]) continue;
v.push_back(rec(it));
}
u32 close = 0;
u32 open = 0;
u32 m = j - i;
for (auto [b, o, c] : v) {
o += b;
close = (close + c + (u64)b * open + (u64)m * o) % mod;
open = (open + o) % mod;
m += b;
// std::cerr << "INT\t" << m << ' ' << open << ' ' << close << '\n';
}
// std::cerr << "CLOSE\t" << p[i].first << ' ' << p[i].second << '\t' << m << ' ' << open << ' ' << close << '\n';
return {m, open, close};
};
return n == 0 ? 0 : std::get<2>(rec(0));
}
int DistanceSum(int n, int x[], int y[]) {
return (foo(n, x, y) + foo(n, y, x)) % mod;
}
