#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},ans;
const ll MOD=1e9;
vector<ll> G[100005];
vector<pll> v;
bitset<100005> vis;
unordered_map<ll,ll> mp;
void DQ(ll l,ll r)
{
if(l==r) return;
ll m=l+r>>1,a,b,sum=0,rsum=0;
DQ(l,m),DQ(m+1,r);
queue<pll> q;
for(a=l;a<=m;++a)
sum=(sum+v[a].F+v[a].S)%MOD;
for(a=l,b=m+1;a<=m&&b<=r;)
if(v[a].S>=v[b].S)
sum=(sum-v[a].F%MOD-v[a].S%MOD+MOD+MOD)%MOD,rsum=(rsum+v[a].F-v[a].S%MOD+MOD)%MOD,q.push(v[a++]);
else
ans=(ans+(v[b].F+v[b].S)*(m-a+1)+(v[b].F-v[b].S)*(a-l)-sum+MOD-rsum+MOD)%MOD,q.push(v[b++]);
while(a<=m)
q.push(v[a++]);
while(b<=r)
ans=(ans+(v[b].F+v[b].S)*(m-a+1)+(v[b].F-v[b].S)*(a-l)-sum+MOD-rsum+MOD)%MOD,q.push(v[b++]);
for(int i=l;i<=r;++i)
v[i]=q.front(),q.pop();
}
int DistanceSum(int N, int *X, int *Y)
{
if(N<=2000)
{
for(int i=0;i<N;++i)
mp[(ll)X[i]<<31|Y[i]]=i;
for(int i=0;i<N;++i)
for(int j=0;j<4;++j)
{
auto p=mp.find(((ll)(X[i]+dx[j])<<31)|(Y[i]+dy[j]));
if(p!=mp.end()) G[i].pb(p->S);
}
for(int i=0;i<N;++i)
{
int tp=0;
queue<pii> q;
q.push(MP(i,0)),vis.reset(),vis[i]=1;
while(!q.empty())
{
auto tmp=q.front();
q.pop(),ans=(ans+tmp.S)%MOD,vis[tmp.F]=1;
for(int j:G[tmp.F])
if(!vis[j]) q.push(MP(j,tmp.S+1)),vis[j]=1;
++tp;
}
}
ans/=2;
}
else
{
for(int i=0;i<N;++i)
v.pb(MP((ll)X[i],(ll)Y[i]));
sort(ALL(v)),DQ(0,N-1);
}
return ans;
}
