#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll> plll;
typedef vector<plll> vplll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vector<pll>> vvpll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e18;
const ll mod = 1e9;
vvll g;
ll ans = 0;
vll dist;
ll n;
void di(ll source) {
dist.assign(n, inf);
dist[source] = 0;
priority_queue<pll, vpll, greater<pll>> pq;
pq.push({0, source});
while (!pq.empty()) {
auto [dis, node] = pq.top();
pq.pop();
for (auto it : g[node]) {
if (dist[it] > dis + 1) {
dist[it] = dis+1;
pq.push({dis+1, it});
}
}
}
}
pll dir[] = {{0,1}, {1,0}, {-1,0} , {0,-1}};
int DistanceSum(int N, int *X, int *Y) {
n=N;
map<pll,ll> id;
g.resize(n);
dist.resize(n);
map<pll,ll> in;
vll sufx(n+1), sufy(n+1);
loop(i,0,n) {
ll x = X[i];
if (x<0) x = -2*x;
X[i] = x;
}
loop(i,0,n) {
ll y = Y[i];
if (y<0) y = -2*y;
Y[i] = y;
}
loop(i,0,n) {
id[{X[i], Y[i]}] =i;
in[{X[i], Y[i]}]++;
}
loopr(i,n,0) {
sufx[i] = sufx[i+1]+X[i];
sufy[i] = sufy[i+1]+Y[i];
}
loop(i,0,n) {
ll x = X[i], y=Y[i];
ll sumx = sufx[i+1];
ll sumy = sufy[i+1];
ll many = (n-i-1);
ans = (ans +abs(sumx - x*many))%mod;
ans = (ans +abs(sumy - y*many))%mod;
}
return ans;
}
/*
3
0 0
0 1
0 2
*/
