#include <bits/stdc++.h>
using namespace std;
struct pii {
int x, y, a, b;
bool operator<(const pii &d) const { return x<d.x || x==d.x && d.y<d.y; }
};
int DistanceSum(int N, int *XX, int *YY) {
vector<pii> A(N);
for(auto&[x,y,a,b]:A) x=*XX++, y=*YY++;
sort(begin(A), end(A));
vector<int> X(N), Y(N);
int n=-1, m=-1, r=0, px=0, py=0;
for(auto&[x,y,a,b]:A) {
X[a=n+=x!=px || y!=py+1]++;
px=x, py=y;
swap(x, y);
}
sort(begin(A), end(A));
px=0, py=0;
vector<set<int>> G(N), H(N);
for(auto&[x,y,a,b]:A) {
if(x==px && y==py+1) G[r].insert(a), G[a].insert(r);
Y[b=m+=x!=px || y!=py+1]++;
px=x, py=y, r=a;
swap(x, y);
}
sort(begin(A), end(A));
px=0, py=0;
for(auto&[x,y,a,b]:A) {
if(x==px && y==py+1) H[r].insert(b), H[b].insert(r);
px=x, py=y, r=b;
}
int s=0;
function<void(int, int)> f1=[&](int i, int p) {
for(int j:G[i]) if(j!=p) f1(j, i), X[i]+=X[j];
s=(s+X[i]*long(N-X[i]))%int(1e9);
};
function<void(int, int)> f2=[&](int i, int p) {
for(int j:H[i]) if(j!=p) f2(j, i), Y[i]+=Y[j];
s=(s+Y[i]*long(N-Y[i]))%int(1e9);
};
f1(0, 0), f2(0, 0);
return s;
}
