#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int NN=1e5;
const int MOD=1e9;
struct Node
{
int id;
int l,r;
int x;
};
pair<int,int> t[NN+10];
vector<Node> tab;
vector<int> e[NN+10];
vector<long long> w[NN+10];
vector<long long> siz[NN+10];
void mknode(int l,int r)
{
//cerr<<"Node"<<tab.size()<<": x="<<t[l].fi<<" l="<<t[l].se<<" r="<<t[r].se<<"\n";
w[tab.size()].resize(r-l+1);
siz[tab.size()].resize(r-l+1);
tab.push_back({tab.size(),t[l].se,t[r].se,t[l].fi});
return;
}
long long merge(int x,int y) // merge y to x
{
//cerr<<"merge Node"<<y<<" to Node"<<x<<": ";
long long ans=0;
int bi=max(0,tab[y].l-tab[x].l),bj=max(0,tab[x].l-tab[y].l);
int ei=bi+min(w[x].size()-bi,w[y].size()-bj),ej=bj+min(w[x].size()-bi,w[y].size()-bj);
//cerr<<"bi="<<bi<<" ei="<<ei<<" bj="<<bj<<" ej="<<ej<<" ";
for(int i=0;i<bj;i++)
{
w[y][i+1]=(w[y][i+1]+siz[y][i]+w[y][i])%MOD;
siz[y][i+1]=(siz[y][i+1]+siz[y][i])%MOD;
}
for(int i=w[y].size()-1;i>=ej;i--)
{
w[y][i-1]=(w[y][i-1]+siz[y][i]+w[y][i])%MOD;
siz[y][i-1]=(siz[y][i-1]+siz[y][i])%MOD;
}
// whole y is in x
long long p=0,s=0,ps=0,ss=0;
for(int i=0;i<bi;i++)
{
p=(p+ps+w[x][i])%MOD;
ps=(ps+siz[x][i])%MOD;
}
for(int i=w[x].size()-1;i>=ei;i--)
{
s=(s+ss+w[x][i])%MOD;
ss=(ss+siz[x][i])%MOD;
}
for(int i=bi,j=bj;i<ei && j<ej;i++,j++)
{
p=(p+ps+w[x][i])%MOD;
ps=(ps+siz[x][i])%MOD;
ans=(ans+p*siz[y][j]+w[y][j]*ps+ps*siz[y][j])%MOD;
}
for(int i=ei-1,j=ej-1;i>=bi && j>=bj;i--,j--)
{
s=(s+ss)%MOD;
ans=(ans+s*siz[y][j]+w[y][j]*ss+ss*siz[y][j])%MOD;
s=(s+w[x][i])%MOD;
ss=(ss+siz[x][i])%MOD;
}
for(int i=bi,j=bj;i<ei && j<ej;i++,j++)
{
siz[x][i]=(siz[x][i]+siz[y][j])%MOD;
w[x][i]=(w[x][i]+w[y][j]+siz[y][j])%MOD;
}
//for(int i=0;i<w[x].size();i++)
// cerr<<"ww["<<i<<"]="<<w[x][i]<<" ss["<<i<<"]="<<siz[x][i]<<" ";
//cerr<<"ans="<<ans<<"\n";
return ans;
}
long long dfs(int x,int p)
{
long long ans=0;
long long tmp=0;
for(int i=tab[x].l;i<=tab[x].r;i++)
{
tmp=(tmp+i-tab[x].l)%MOD;
ans=(ans+tmp)%MOD;
}
fill(w[x].begin(),w[x].end(),0);
fill(siz[x].begin(),siz[x].end(),1);
for(auto v:e[x])
{
if(v==p)
continue;
ans+=dfs(v,x);
ans+=merge(x,v);
ans%=MOD;
}
return ans;
}
int DistanceSum(int N,int *X,int *Y)
{
int n=N;
for(int i=0;i<n;i++)
t[i+1]={X[i],Y[i]};
sort(t+1,t+n+1);
int bg=1;
for(int i=1;i<=n;i++)
{
if(i!=1 && (t[i-1].fi!=t[i].fi || t[i-1].se+1!=t[i].se))
{
mknode(bg,i-1);
bg=i;
}
}
mknode(bg,n);
int m=tab.size();
for(int i=0,j=0;i<m;i++)
{
while(j<m && (tab[j].x<tab[i].x-1 || tab[j].r<tab[i].l))
j++;
while(j<m && tab[j].x==tab[i].x-1 && tab[j].l<=tab[i].r)
{
//cerr<<"link Node"<<i<<" Node"<<j<<"\n";
e[i].push_back(j);
e[j].push_back(i);
j++;
}
if(j>0)
j--;
}
long long ans=dfs(0,-1);
return (ans+MOD)%MOD;
}
