#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple <ll,ll,ll> plll;
typedef vector <plll> vplll;
typedef pair <ll,ll> pll;
typedef vector <ll> vll;
typedef vector <pll> vpll;
typedef vector <vector <pll>> vvpll;
typedef vector <vector <ll>> vvll;
typedef vector <bool> vb;
typedef vector <vector <bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e9 + 7;
const ll mod = 1e9;
vvll gh, gv;
vll wh, wv;
vll sh, sv;
ll th, tv, n, res;
ll dfsh(ll u, ll p) {
ll s = wh[u];
for (ll v : gh[u]) if (v != p) s += dfsh(v, u);
sh[u] = s;
if (p != -1) res = (res + (s * (th - s)) % mod) % mod;
return s;
}
ll dfsv(ll u, ll p) {
ll s = wv[u];
for (ll v : gv[u]) if (v != p) s += dfsv(v, u);
sv[u] = s;
if (p != -1) res = (res + (s * (tv - s)) % mod) % mod;
return s;
}
int DistanceSum(int nn, int *x, int *y) {
res = 0;
n = nn;
map<ll, vector<pair<ll,int>>> rw, cw;
loop(i,0,n) {
rw[x[i]].push_back({y[i],i});
cw[y[i]].push_back({x[i],i});
}
int hc = 0, vc = 0;
vector<int> ih(n), iv(n);
vector<ll> hl, hh, vl, vh;
wh.clear(); wv.clear();
map<ll, vector<int>> rseg, cseg;
for (auto &pr : rw) {
auto &v = pr.second; sort(all(v));
int sz = v.size(), st = 0;
loop(i,1,sz+1) {
if (i == sz || v[i].first != v[i-1].first+1) {
hl.push_back(v[st].first);
hh.push_back(v[i-1].first);
ll cnt = i - st;
wh.push_back(cnt);
rseg[pr.first].push_back(hc);
loop(j,st,i) ih[v[j].second] = hc;
hc++;
st = i;
}
}
}
for (auto &pc : cw) {
auto &v = pc.second; sort(all(v));
int sz = v.size(), st = 0;
loop(i,1,sz+1) {
if (i == sz || v[i].first != v[i-1].first+1) {
vl.push_back(v[st].first);
vh.push_back(v[i-1].first);
ll cnt = i - st;
wv.push_back(cnt);
cseg[pc.first].push_back(vc);
loop(j,st,i) iv[v[j].second] = vc;
vc++;
st = i;
}
}
}
gh.assign(hc, vll());
for (auto it = rseg.begin(); it != rseg.end(); ++it) {
auto jt = next(it);
if (jt != rseg.end() && jt->first == it->first+1) {
auto &uL = it->second, &vL = jt->second;
int i1 = 0, j1 = 0;
while (i1 < (int)uL.size() && j1 < (int)vL.size()) {
int u = uL[i1], v = vL[j1];
if (hh[u] < hl[v]) i1++;
else if (hh[v] < hl[u]) j1++;
else {
gh[u].push_back(v);
gh[v].push_back(u);
if (hh[u] < hh[v]) i1++;
else j1++;
}
}
}
}
gv.assign(vc, vll());
for (auto it = cseg.begin(); it != cseg.end(); ++it) {
auto jt = next(it);
if (jt != cseg.end() && jt->first == it->first+1) {
auto &uL = it->second, &vL = jt->second;
int i1 = 0, j1 = 0;
while (i1 < (int)uL.size() && j1 < (int)vL.size()) {
int u = uL[i1], v = vL[j1];
if (vh[u] < vl[v]) i1++;
else if (vh[v] < vl[u]) j1++;
else {
gv[u].push_back(v);
gv[v].push_back(u);
if (vh[u] < vh[v]) i1++;
else j1++;
}
}
}
}
th = 0; loop(i,0,hc) th += wh[i];
sh.assign(hc,0);
if (hc > 0) dfsh(0, -1);
tv = 0; loop(i,0,vc) tv += wv[i];
sv.assign(vc,0);
if (vc > 0) dfsv(0, -1);
return res;
}
