// ~ Be Name Khoda ~ //
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 5e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 2e3 + 10;
const int mod = 1e9;
const ll inf = 1e18;
int h[maxn3], q[maxn3];
vector <int> adj[maxn5];
map <pair<ll, ll>, int> p;
vector <ll> avx, avy;
inline int solve(int n, int *x, int *y){
for(int i = 0; i < n; i++)
p[{x[i], y[i]}] = i;
for(int i = 0; i < n; i++){
if(p.find(mp(x[i] - 1, y[i])) != p.end())
adj[i].pb(p[{x[i] - 1, y[i]}]);
if(p.find(mp(x[i] + 1, y[i])) != p.end())
adj[i].pb(p[{x[i] + 1, y[i]}]);
if(p.find(mp(x[i], y[i] - 1)) != p.end())
adj[i].pb(p[{x[i], y[i] - 1}]);
if(p.find(mp(x[i], y[i] + 1)) != p.end())
adj[i].pb(p[{x[i], y[i] + 1}]);
}
ll ans = 0;
for(int i = 0; i < n; i++){
memset(h, -1, sizeof h);
int l = 0, r = 1;
q[0] = i;
h[i] = 0;
while(l < r){
int v = q[l++];
ans += h[v];
for(auto u : adj[v]) if(h[u] == -1){
h[u] = h[v] + 1;
q[r++] = u;
}
}
}
ans /= 2;
return ans % mod;
}
int DistanceSum(int n, int *x, int *y){
if(n <= 2000)
return solve(n, x, y);
for(int i = 0; i < n; i++){
avx.pb(x[i]);
avy.pb(y[i]);
}
sort(all(avx));
sort(all(avy));
ll psx = avx[0], psy = avy[0];
ll ans = 0;
for(ll i = 1; i < n; i++){
ans += i * avx[i] - psx; ans %= mod;
ans += i * avy[i] - psy; ans %= mod;
psx += avx[i];
psy += avy[i];
}
return ans % mod;
}
