#include <bits/stdc++.h>
// mrrrowwww meeowwwww :3
// go play vivid/stasis! !! !!! https://vividstasis.gay
#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;
int ____init = []{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
return 0;
}();
const int MOD = 1000000000;
struct Node {
int size;
vector<int> adj;
};
pair<int, int> get(const vector<Node> &tree, int n, int i, int p=-1) {
int total_size = tree[i].size;
long long res = 0;
for (int j : tree[i].adj) {
if (j == p) continue;
auto [child_total_size, child_res] = get(tree, n, j, i);
total_size += child_total_size;
res += child_res;
}
res += (long long) total_size * (n - total_size);
return {total_size, res % MOD};
}
vector<Node> get_tree(vector<pair<int, int>> &cells) {
vector<Node> tree;
vector<pair<pair<int, int>, int>> ranges;
for (int i = 0, j = 0; i < cells.size(); j = i) {
for (i++; i < cells.size() && cells[i].f == cells[j].f; i++);
vector<pair<pair<int, int>, int>> new_ranges;
for (int k = j, l = j, m = 0; k < i; l = k) {
for (k++; k < i && cells[k].s == cells[k - 1].s + 1; k++);
int start = cells[l].s, end = cells[k - 1].s;
int node = tree.size(); tree.pb({ .size = k - l });
new_ranges.pb({{start, end}, node});
for (; m < ranges.size() && ranges[m].f.f <= end; m++) {
if (ranges[m].f.s >= start) {
tree[ranges[m].s].adj.pb(node);
tree[node].adj.pb(ranges[m].s);
}
}
if (m) m--;
}
ranges = new_ranges;
}
return tree;
}
int DistanceSum(int n, int x[], int y[]) {
int res = 0;
{
vector<pair<int, int>> cells_x_y;
fo(i, 0, n) cells_x_y.pb({x[i], y[i]});
sort(be(cells_x_y));
res += get(get_tree(cells_x_y), n, 0).s;
}
{
vector<pair<int, int>> cells_y_x;
fo(i, 0, n) cells_y_x.pb({y[i], x[i]});
sort(be(cells_y_x));
res += get(get_tree(cells_y_x), n, 0).s;
}
return res % MOD;
}
