#include <bits/stdc++.h>
#define forn(i, a, b) for(int i = int (a); i <= int(b); ++ i)
#define fora(i, a, b) for(int i = int (a); i >= int(b); -- i)
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
const int maxn = 1e5;
const int mx[4] = {0, 0, 1, -1};
const int my[4] = {1, -1, 0, 0};
map<pii, int> mapa;
set<int> aux[maxn];
vi treex[maxn];
vi treey[maxn];
int szx[maxn];
int szy[maxn];
int compx[maxn];
int compy[maxn];
int arre[maxn][4];
bool visitadox[maxn];
bool visitadoy[maxn];
ll res;
int n;
ll mod = 1e9;
void dfsx(int u, int p){
for(auto v : treex[u]){
if(v != p){
dfsx(v, u);
res += ((ll) n - (ll) szx[v]) * (ll) szx[v];
res %= mod;
szx[u] += szx[v];
}
}
}
void dfsy(int u, int p){
for(auto v : treey[u]){
if(v != p){
dfsy(v, u);
res += ((ll) n - (ll) szy[v]) * (ll) szy[v];
res %= mod;
szy[u] += szy[v];
}
}
}
void moverme(int i, int compo, int ini){
while(ini != -1){
if(i <= 1){
compy[ini] = compo;
visitadoy[ini] = 1;
}
else{
compx[ini] = compo;
visitadox[ini] = 1;
}
ini = arre[ini][i];
}
}
int DistanceSum(int N, int *X, int *Y) {
n = N;
forn(i, 0, N - 1){
mapa[mp(X[i], Y[i])] = i;
}
memset(arre, -1, sizeof(arre));
forn(i, 0, N - 1){
forn(j, 0, 3){
if(mapa.count(mp(X[i] + mx[j], Y[i] + my[j]))){
arre[i][j] = mapa[mp(X[i] + mx[j], Y[i] + my[j])];
}
}
}
///x
int compox = -1, compoy = -1;
forn(i, 0, N - 1){
if(!visitadoy[i]){
moverme(0, ++ compoy, i);
moverme(1, compoy, i);
}
if(!visitadox[i]){
moverme(2, ++ compox, i);
moverme(3, compox, i);
}
}
///visitado y
forn(i, 0, N - 1){
forn(j, 2, 3){
if(mapa.count(mp(X[i] + mx[j], Y[i] + my[j]))){
aux[compy[i]].insert(compy[mapa[mp(X[i] + mx[j], Y[i] + my[j])]]);
}
}
}
forn(i, 0, compoy){
for(auto j : aux[i]){
treey[i].pb(j);
}
aux[i].clear();
}
forn(i, 0, N - 1){
forn(j, 0, 1){
if(mapa.count(mp(X[i] + mx[j], Y[i] + my[j]))){
aux[compx[i]].insert(compx[mapa[mp(X[i] + mx[j], Y[i] + my[j])]]);
}
}
szx[compx[i]] ++;
szy[compy[i]] ++;
}
forn(i, 0, compox){
for(auto j : aux[i]){
treex[i].pb(j);
}
aux[i].clear();
}
dfsx(0, 0);
dfsy(0, 0);
return (int) res;
}
