#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
template <class T>
void rd(T &x) {
int sgn = 1;
char ch;
x = 0;
for (ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar()) ;
if (ch == '-') ch = getchar(), sgn = -1;
for (; '0' <= ch && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
x *= sgn;
}
template <class T>
void wr(T x) {
if (x < 0) putchar('-'), wr(-x);
else if (x < 10) putchar(x + '0');
else wr(x / 10), putchar(x % 10 + '0');
}
void usaco(string s){
freopen((s+".in").c_str(), "r", stdin);
freopen((s+".out").c_str(), "w", stdout);
}
/*
think of it as a tree
we dont need to acc for each node
we keep track of hor and ver
for children of node
we add child dist + (sum of alldist without that child)
dist can be split as hor and ver can be handled separately
but how to implement
because dist remains const
we use that fact
how to maintain cleanly
each node can go hor or ver
if both hor ver or other sides then treat each as subtree
for each node we keep count of vals coming to it
so we can add those to our subtree
dist trav hor dist trav ver is the parent stuff
but at each node we need to add 1 + 2 + 3 - - - n
n(n+1)/2 added each time?
no
at each level theres certain number of nodes
so we need to somehow take that into account
when we go down ver
we have to add it num of times we visited it horizontally
when we go down more we just add hor to it that will take in account the going down
by 1 vertically
work backwards?
hor tree ver tree
*/
const int maxn = 1e5 + 5, MOD = 1e9;;
vector<pair<int, int>> a;
ll ans = 0, n;
int tls[maxn], csize[maxn];
multiset<int> adj[maxn];
vector<bool> vis(maxn, 0);
void dfs(int u){
vis[u] = 1;
//cerr << u << '\n';
for(auto c : adj[u]){
if(!vis[c]){
dfs(c);
csize[u] += csize[c];
}
}
ans = (ans + (1ll * csize[u] * (n - csize[u])) % MOD) % MOD;
}
void solve(){
int i = 0, m = 0;
sort(a.begin(),a.end());
rep(i, 0, n){
adj[i].clear();
}
while(i < n){
int j = i + 1; tls[i] = m;
while(j < n and a[j] == make_pair(a[j - 1].first, a[j - 1].second + 1)){
//cerr << j << ' ' << tls[j] << ' ' << m << '\n';
tls[j++] = m;
}
csize[m] = j - i; i = j;
//cerr << i << ' ' << csize[m] << '\n';
m++;
}
cerr << "hello";
int j = 0;
rep(i, 0, n){
for(; j < n and a[j] < make_pair(a[i].first - 1 , a[i].second); j++){cerr<<"hi";}
if(j < n and a[j] == make_pair(a[i].first - 1 , a[i].second)){
//cerr << tls[i] << " -> " << tls[j] << '\n';
adj[tls[i]].insert(tls[j]);
adj[tls[j]].insert(tls[i]);
}
}
rep(i, 0, (int)vis.size()){
vis[i] = 0;
}
dfs(0);
}
int DistanceSum(int N, int *X, int *Y) {
n = N;
rep(i, 0, n){
a.emplace_back(X[i], Y[i]);
}
solve();
rep(i, 0, n){
//easy way to do it is to just rev coord
//a[i].first =
swap(a[i].first,a[i].second);
}
solve();
return ans % MOD;
}
/*
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
#ifdef LOCAL_DEFINE
freopen("input.txt", "r", stdin);
#endif
}
*/
