#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
using namespace std;
int N;
vector<int> X, Y;
const int MX = 100'000;
const int INF = 1'000'000'000;
struct point{
int x;
int y;
int i;
int rightNodes;
int downNodes;
};
bool operator < (point A, point B){
if(A.x != B.x) return A.x < B.x;
return A.y < B.y;
}
set<point> P;
int getIndex(int x, int y){
set<point>::iterator f = P.find(point{x, y, -1, -1, -1});
if(f == P.end()) return -1;
else return f->i;
}
long long new_ans = 0;
vector<int> up_edge[1+MX];
vector<int> down_edge[1+MX];
vector<int> Y_index_size(1+MX);
vector<int> Y_index_coord(1+MX);
int Y_max_index;
vector<int> Y_parent(1+MX);
vector<int> Y_subtree_sum(1+MX);
vector<int> point_Y_line(1+MX);
void Y_dfs(int u, int p){
Y_subtree_sum[u] = Y_index_size[u];
for(int v: up_edge[u]){
if(v == p) continue;
Y_parent[v] = u;
Y_dfs(v, u);
Y_subtree_sum[u] += Y_subtree_sum[v];
}
for(int v: down_edge[u]){
if(v == p) continue;
Y_parent[v] = u;
Y_dfs(v, u);
Y_subtree_sum[u] += Y_subtree_sum[v];
}
}
vector<int> left_edge[1+MX];
vector<int> right_edge[1+MX];
vector<int> X_index_size(1+MX);
vector<int> X_index_coord(1+MX);
int X_max_index;
vector<int> X_parent(1+MX);
vector<int> X_subtree_sum(1+MX);
vector<int> point_X_line(1+MX);
void X_dfs(int u, int p){
X_subtree_sum[u] = X_index_size[u];
for(int v: left_edge[u]){
if(v == p) continue;
X_parent[v] = u;
X_dfs(v, u);
X_subtree_sum[u] += X_subtree_sum[v];
}
for(int v: right_edge[u]){
if(v == p) continue;
X_parent[v] = u;
X_dfs(v, u);
X_subtree_sum[u] += X_subtree_sum[v];
}
}
long long init_dist = 0;
vector<int> dx{0, 0, +1, -1};
vector<int> dy{+1, -1, 0, 0};
vector<bool> visit(MX, 0);
int DistanceSum(int N_, int *X_, int *Y_){
N = N_;
X = vector<int>(N);
Y = vector<int>(N);
for(int i = 0; i < N; i++){
X[i] = X_[i];
Y[i] = Y_[i];
}
int Xmin = X[0], Ymin = Y[0];
for(int i = 1; i < N; i++){
Xmin = min(Xmin, X[i]);
Ymin = min(Ymin, Y[i]);
}
for(int i = 0; i < N; i++){
X[i] = X[i] - Xmin + 1;
Y[i] = Y[i] - Ymin + 1;
}
for(int i = 0; i < N; i++)
P.insert(point{X[i], Y[i], i, -1, -1});
vector<int> Ylist[1+MX];
for(int i = 0; i < N; i++)
Ylist[ X[i] ].push_back(Y[i]);
for(int x = 1; x <= MX; x++)
sort(Ylist[x].begin(), Ylist[x].end());
int curr_Y_index = 0;
vector<int> Y_begin[1+MX], Y_end[1+MX];
vector<int>* Y_index = new vector<int>[1+MX];
for(int x = 1; x <= MX; x++){
if(Ylist[x].empty()) continue;
Y_begin[x].push_back(Ylist[x][0]);
curr_Y_index++;
Y_index[x].push_back(curr_Y_index);
for(int i = 1; i < (int)Ylist[x].size(); i++){
if(Ylist[x][i-1] + 1 != Ylist[x][i]){
Y_end[x].push_back(Ylist[x][i-1]);
Y_begin[x].push_back(Ylist[x][i]);
curr_Y_index++;
Y_index[x].push_back(curr_Y_index);
}
}
Y_end[x].push_back(Ylist[x].back());
for(int v = 0; v < (int)Y_begin[x].size(); v++){
Y_index_size[ Y_index[x][v] ] = Y_end[x][v] - Y_begin[x][v] + 1;
Y_index_coord[ Y_index[x][v] ] = x;
for(int y = Y_begin[x][v]; y <= Y_end[x][v]; y++)
point_Y_line[ getIndex(x, y) ] = Y_index[x][v];
}
}
for(int x = 1; x+1 <= MX; x++){
if(Y_index[x].empty() || Y_index[x+1].empty()) continue;
int q = 0;
for(int p = 0; p < (int)Y_index[x].size(); p++){
if(max(Y_begin[x][p], Y_begin[x+1][q]) <= min(Y_end[x][p], Y_end[x+1][q])){
down_edge[Y_index[x][p]].push_back(Y_index[x+1][q]);
up_edge[Y_index[x+1][q]].push_back(Y_index[x][p]);
}
while(q+1 < (int)Y_begin[x+1].size() && Y_begin[x+1][q+1] <= Y_end[x][p]){
q++;
if(max(Y_begin[x][p], Y_begin[x+1][q]) <= min(Y_end[x][p], Y_end[x+1][q])){
down_edge[Y_index[x][p]].push_back(Y_index[x+1][q]);
up_edge[Y_index[x+1][q]].push_back(Y_index[x][p]);
}
}
}
}
Y_max_index = curr_Y_index;
Y_parent[1] = 0;
Y_dfs(1, 1);
for(int u = 1; u <= Y_max_index; u++){
for(int v: down_edge[u]){
if(v == Y_parent[u])
new_ans += (long long)Y_subtree_sum[u] * (long long)(N - Y_subtree_sum[u]);
else
new_ans += (long long)Y_subtree_sum[v] * (long long)(N - Y_subtree_sum[v]);
}
}
vector<int>* Xlist = new vector<int>[1+MX];
for(int i = 0; i < N; i++)
Xlist[ Y[i] ].push_back(X[i]);
for(int y = 1; y <= MX; y++)
sort(Xlist[y].begin(), Xlist[y].end());
int curr_X_index = 0;
vector<int>* X_begin = new vector<int>[1+MX];
vector<int>* X_end = new vector<int>[1+MX];
vector<int>* X_index = new vector<int>[1+MX];
for(int y = 1; y <= MX; y++){
if(Xlist[y].empty()) continue;
X_begin[y].push_back(Xlist[y][0]);
curr_X_index++;
X_index[y].push_back(curr_X_index);
for(int i = 1; i < (int)Xlist[y].size(); i++){
if(Xlist[y][i-1] + 1 != Xlist[y][i]){
X_end[y].push_back(Xlist[y][i-1]);
X_begin[y].push_back(Xlist[y][i]);
curr_X_index++;
X_index[y].push_back(curr_X_index);
}
}
X_end[y].push_back(Xlist[y].back());
for(int v = 0; v < (int)X_begin[y].size(); v++){
X_index_size[ X_index[y][v] ] = X_end[y][v] - X_begin[y][v] + 1;
X_index_coord[ X_index[y][v] ] = y;
for(int x = X_begin[y][v]; x <= X_end[y][v]; x++)
point_X_line[ getIndex(x, y) ] = X_index[y][v];
}
}
for(int y = 1; y+1 <= MX; y++){
if(X_index[y].empty() || X_index[y+1].empty()) continue;
int q = 0;
for(int p = 0; p < (int)X_index[y].size(); p++){
if(max(X_begin[y][p], X_begin[y+1][q]) <= min(X_end[y][p], X_end[y+1][q])){
right_edge[X_index[y][p]].push_back(X_index[y+1][q]);
left_edge[X_index[y+1][q]].push_back(X_index[y][p]);
}
while(q+1 < (int)X_begin[y+1].size() && X_begin[y+1][q+1] <= X_end[y][p]){
q++;
if(max(X_begin[y][p], X_begin[y+1][q]) <= min(X_end[y][p], X_end[y+1][q])){
right_edge[X_index[y][p]].push_back(X_index[y+1][q]);
left_edge[X_index[y+1][q]].push_back(X_index[y][p]);
}
}
}
}
X_max_index = curr_X_index;
X_parent[1] = 0;
X_dfs(1, 1);
for(int u = 1; u <= X_max_index; u++)
{
for(int v: right_edge[u])
{
if(v == X_parent[u])
new_ans += (long long)X_subtree_sum[u] * (long long)(N - X_subtree_sum[u]);
else
new_ans += (long long)X_subtree_sum[v] * (long long)(N - X_subtree_sum[v]);
}
}
return int(new_ans % 1'000'000'000LL);
}
