#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;
static int id_counter = 0;
struct Node {
int id;
int size;
vector<shared_ptr<Node>> children;
pair<int, int> get(int n, int p=-1) {
int total_size = size;
long long res = 0;
for (const shared_ptr<Node> child : children) {
if (child->id == p) continue;
auto [child_total_size, child_res] = child->get(n, id);
total_size += child_total_size;
res += child_res;
}
res += (long long) total_size * (n - total_size);
return {total_size, res % MOD};
}
};
shared_ptr<Node> get_tree(vector<pair<int, int>> &cells) {
shared_ptr<Node> root;
vector<pair<pair<int, int>, shared_ptr<Node>>> 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>, shared_ptr<Node>>> 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;
shared_ptr<Node> node = make_shared<Node>(Node { .id = id_counter++, .size = k - l });
if (!root) root = node;
new_ranges.pb({{start, end}, node});
for (; m < ranges.size() && ranges[m].f.f <= end; m++) {
if (ranges[m].f.s >= start) {
ranges[m].s->children.pb(node);
node->children.pb(ranges[m].s);
}
}
if (m) m--;
}
ranges = new_ranges;
}
return root;
}
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_tree(cells_x_y)->get(n).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_tree(cells_y_x)->get(n).s;
}
return res % MOD;
}
