#include <bits/stdc++.h>
using namespace std;
struct State {
uint32_t sum = 0;
uint32_t total_count = 0;
vector<tuple<int32_t,int32_t,uint32_t>> ranges;
State() {
sum = 0;
total_count = 0;
ranges.clear();
}
void next_step(size_t n, const set<int32_t>& v) {
total_count += (uint32_t)v.size();
vector<tuple<int32_t,int32_t,uint32_t>> new_ranges;
tuple<int32_t,int32_t,uint32_t> new_range = {-1, -1, 0};
size_t j = 0;
while (j < ranges.size() && get<0>(ranges[j]) == -1) j++;
for (int32_t i : v) {
if (i <= get<1>(new_range) + 1) {
get<1>(new_range) = max(get<1>(new_range), i);
get<2>(new_range) += 1;
} else {
if (get<0>(new_range) != -1) {
new_ranges.push_back(new_range);
}
new_range = {i, i, 1};
}
while (j < ranges.size() &&
get<0>(ranges[j]) <= get<1>(new_range) + 1)
{
// trim left
for (int k = get<0>(ranges[j]); k < get<1>(ranges[j]); k++) {
if (v.count(k)) {
get<0>(ranges[j]) = k;
break;
}
}
// trim right
for (int k = get<1>(ranges[j]); k > get<0>(ranges[j]); k--) {
if (v.count(k)) {
get<1>(ranges[j]) = k;
break;
}
}
if (get<0>(ranges[j]) > get<1>(new_range) + 1)
break;
if (get<0>(new_range) <= get<1>(ranges[j]) + 1) {
get<0>(new_range) = min(get<0>(new_range), get<0>(ranges[j]));
get<1>(new_range) = max(get<1>(new_range), get<1>(ranges[j]));
get<2>(new_range) += get<2>(ranges[j]);
} else {
new_ranges.push_back(ranges[j]);
}
j++;
}
}
if (get<0>(new_range) != -1)
new_ranges.push_back(new_range);
while (j < ranges.size() &&
get<0>(ranges[j]) <= get<1>(new_range) + 1)
{
for (int k = get<0>(ranges[j]); k < get<1>(ranges[j]); k++) {
if (v.count(k)) {
get<0>(ranges[j]) = k;
break;
}
}
for (int k = get<1>(ranges[j]); k > get<0>(ranges[j]); k--) {
if (v.count(k)) {
get<1>(ranges[j]) = k;
break;
}
}
new_ranges.push_back(ranges[j]);
j++;
}
ranges = move(new_ranges);
uint64_t curr_sum =
(uint64_t)total_count * ((uint64_t)n + total_count);
for (auto &r : ranges) {
uint64_t x = get<2>(r);
curr_sum -= 2 * x * x;
}
sum = (sum + (curr_sum % 1000000000ULL)) % 1000000000ULL;
}
};
uint32_t solve(const vector<pair<int32_t,int32_t>>& input) {
map<int32_t, set<int32_t>> x_to_y, y_to_x;
for (auto &[x, y] : input) {
x_to_y[x].insert(y);
y_to_x[y].insert(x);
}
uint64_t res = 0;
// horizontal
{
uint64_t res_horiz = 0;
{
State s;
for (auto &p : x_to_y)
s.next_step(input.size(), p.second);
res_horiz += s.sum;
}
{
State s;
for (auto it = x_to_y.rbegin(); it != x_to_y.rend(); ++it)
s.next_step(input.size(), it->second);
res_horiz += s.sum;
}
res = (res + (res_horiz / 2) % 1000000000ULL) % 1000000000ULL;
}
// vertical
{
uint64_t res_vert = 0;
{
State s;
for (auto &p : y_to_x)
s.next_step(input.size(), p.second);
res_vert += s.sum;
}
{
State s;
for (auto it = y_to_x.rbegin(); it != y_to_x.rend(); ++it)
s.next_step(input.size(), it->second);
res_vert += s.sum;
}
res = (res + (res_vert / 2) % 1000000000ULL) % 1000000000ULL;
}
return res % 1000000000ULL;
}
int DistanceSum(int n, int x[], int y[]) {
vector<pair<int32_t, int32_t>> input;
for (int i = 0; i < n; i++) input.push_back({x[i], y[i]});
return solve(input);
}
