#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;
loop(i,0,n) {
id[{X[i], Y[i]}] =i;
in[{X[i], Y[i]}]++;
}
loop(i,0,n) {
ll x = X[i], y=Y[i];
loop(j,i+1,n) {
ans = (ans+abs(x-X[j])+abs(y-Y[j]))%mod;
}
}
return ans;
}
