#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
const ll MOD = (ll)(1e9);
const ll INF = INT_MAX;
typedef pair<ll,ll> ii;
map<ii,ll> nodes;
ll adj[100005][4],dist[100005],xs[]={0,0,-1,1},ys[]={1,-1,0,0},n,pos[100005];
ll fen[3][100005];
void update(ll t,ll idx,ll val){
for (ll i = idx; i <= n; i+=(i&(-i)))
fen[t][i]=(fen[t][i]+val)%MOD;
}
ll get(ll t,ll idx){
ll h=0;
for (ll i = idx; i >= 1; i-=(i&(-i)))
h=(h+fen[t][i])%MOD;
return h;
}
ll sum(ll t,ll a,ll b){
return (get(t,b)-get(t,a-1)+MOD)%MOD;
}
int DistanceSum(int N, int *X, int *Y) {
n=N;
ll ans=0;
if(N<=2000){
memset(adj,-1,sizeof adj);
for (ll i = 0; i < N; ++i)
nodes[{X[i],Y[i]}]=i;
for (ll i = 0; i < N; ++i)
for (ll d = 0; d < 4; ++d)
if(nodes.count({X[i]+xs[d],Y[i]+ys[d]}))
adj[i][d]=nodes[{X[i]+xs[d],Y[i]+ys[d]}];
for (ll i = 0; i < N; ++i)
{
queue<ll> q;
for (ll j = 0; j < N; ++j)dist[j]=INF;
q.push(i);
dist[i]=0;
while(!q.empty()){
ll f=q.front();
q.pop();
for (ll d = 0; d < 4; ++d)
if(adj[f][d]!=-1 && dist[adj[f][d]]==INF){
dist[adj[f][d]]=dist[f]+1,q.push(adj[f][d]);
if(dist[adj[f][d]]>=MOD)dist[adj[f][d]]%=MOD;
}
}
for (ll j = i+1; j < N; ++j)
{
ans+=dist[j];
if(ans>=MOD)ans%=MOD;
}
}
}
else{
vector<ii> vec(N),vecX(N);
for (ll i = 0; i < N; ++i){
vec[i]={Y[i],i};
vecX[i]={X[i],i};
}
sort(vec.begin(),vec.end());
sort(vecX.begin(),vecX.end());
for (ll i = 1; i <= N; ++i){
ll k=vecX[i-1].se;
pos[k]=i;
update(0,i,1),update(1,i,((X[k])%MOD+(Y[k])%MOD)%MOD),update(2,i,(Y[k]-(X[k])%MOD+(MOD))%MOD);
}
for (ll i = 1; i <= N; ++i)
{
ll id=vec[i-1].se,y=(vec[i-1].fi%MOD);
update(0,pos[id],-1),update(1,pos[id],(MOD-(X[id]%MOD+Y[id]%MOD)%MOD)%MOD),update(2,pos[id],((X[id])%MOD-(Y[id]%MOD)+MOD)%MOD);
for (ll z = 0; z < 3; ++z)
assert(sum(z,pos[id],pos[id])==0);
ans=(ans+(sum(1,pos[id],n)-((sum(0,pos[id],n)*(((X[id])%MOD+y)%MOD))%MOD) + MOD)%MOD)%MOD;
ans=(ans+(sum(2,1,pos[id])+((sum(0,1,pos[id])*(((X[id])%MOD-y+MOD)%MOD))%MOD))%MOD)%MOD;
}
}
return (ll)ans;
}
