#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const ll MOD = 1e9;
struct Point
{
int x, y;
};
int N;
ll ans;
Point A[MAXN+10];
vector<int> point1[MAXN+10];
vector<int> l1[MAXN+10], r1[MAXN+10], k1[MAXN+10];
vector<int> adj1[MAXN+10];
vector<int> point2[MAXN+10];
vector<int> l2[MAXN+10], r2[MAXN+10], k2[MAXN+10];
vector<int> adj2[MAXN+10];
ll sz[MAXN+10], sum[MAXN+10], val[MAXN+10];
void dfs(int now, int bef, int depth, vector<int> *adj)
{
sum[now]=depth*val[now];
sz[now]=val[now];
/*
printf("%d : ", now);
for(int nxt : adj[now]) printf("%d ", nxt);
printf("\n");
*/
for(int nxt : adj[now])
{
if(nxt==bef) continue;
dfs(nxt, now, depth+1, adj);
sum[now]+=sum[nxt];
sz[now]+=sz[nxt];
}
//printf("%d %d %lld %lld\n", now, depth, sz[now], sum[now]);
ll x=0;
x+=sum[now]-depth*sz[now];
for(int nxt : adj[now])
{
if(nxt==bef) continue;
x+=(sum[nxt]-depth*sz[nxt])*(sz[now]-sz[nxt]-1);
x%=MOD;
}
//printf("%lld\n", x);
ans+=x;
}
int DistanceSum(int _N, int *X, int *Y)
{
int i, j, k;
N=_N;
for(i=1; i<=N; i++) A[i]={X[i-1], Y[i-1]};
int minx=2147483647, miny=2147483647;
for(i=1; i<=N; i++) minx=min(minx, A[i].x);
for(i=1; i<=N; i++) miny=min(miny, A[i].y);
minx--; miny--;
for(i=1; i<=N; i++) A[i].x-=minx, A[i].y-=miny;
for(i=1; i<=N; i++) point1[A[i].x].push_back(A[i].y);
int cnt=1;
for(i=1; i<=N; i++)
{
if(point1[i].empty()) break;
sort(point1[i].begin(), point1[i].end());
l1[i].push_back(point1[i][0]);
k1[i].push_back(cnt++);
for(j=1; j<point1[i].size(); j++)
{
int x=point1[i][j-1], y=point1[i][j];
if(x+1<y)
{
r1[i].push_back(x);
val[k1[i].back()]=r1[i].back()-l1[i].back()+1;
l1[i].push_back(y);
k1[i].push_back(cnt++);
}
}
r1[i].push_back(point1[i].back());
val[k1[i].back()]=r1[i].back()-l1[i].back()+1;
}
for(i=2; i<=N; i++)
{
if(point1[i].empty()) break;
for(j=0; j<l1[i].size(); j++)
{
int p=lower_bound(r1[i-1].begin(), r1[i-1].end(), l1[i][j])-r1[i-1].begin();
int q=upper_bound(l1[i-1].begin(), l1[i-1].end(), r1[i][j])-l1[i-1].begin();
for(k=p; k<q; k++) adj1[k1[i][j]].push_back(k1[i-1][k]), adj1[k1[i-1][k]].push_back(k1[i][j]);
}
}
dfs(1, 1, 0, adj1);
//printf("======================\n");
for(i=1; i<=N; i++) point2[A[i].y].push_back(A[i].x);
cnt=1;
for(i=1; i<=N; i++)
{
if(point2[i].empty()) break;
sort(point2[i].begin(), point2[i].end());
l2[i].push_back(point2[i][0]);
k2[i].push_back(cnt++);
for(j=1; j<point2[i].size(); j++)
{
int x=point2[i][j-1], y=point2[i][j];
if(x+1<y)
{
r2[i].push_back(x);
val[k2[i].back()]=r2[i].back()-l2[i].back()+1;
l2[i].push_back(y);
k2[i].push_back(cnt++);
}
}
r2[i].push_back(point2[i].back());
val[k2[i].back()]=r2[i].back()-l2[i].back()+1;
}
for(i=2; i<=N; i++)
{
if(point2[i].empty()) break;
for(j=0; j<l2[i].size(); j++)
{
int p=lower_bound(r2[i-1].begin(), r2[i-1].end(), l2[i][j])-r2[i-1].begin();
int q=upper_bound(l2[i-1].begin(), l2[i-1].end(), r2[i][j])-l2[i-1].begin();
for(k=p; k<q; k++) adj2[k2[i][j]].push_back(k2[i-1][k]), adj2[k2[i-1][k]].push_back(k2[i][j]);
}
}
dfs(1, 1, 0, adj2);
return ans;
}
