#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll res = 0;
void sum(vector<ll> &x, vector<ll> &preX, ll X) {
ll idx = lower_bound(x.begin(), x.end(), X) - x.begin();
if (idx) {
res += (idx + 1) * X - preX[idx];
}
if (idx != preX.size()) {
res += (preX.back() - (!idx ? 0 : preX[idx - 1])) - 1ll * (preX.size() - idx) * X;
}
}
vector<ll> preX, preY, x, y;
map< pair<int, int> , int > got;
int cost[2100];
vector<int> adj[2100];
int dx[4] = {0, 0, -1, 1};
int dy[4] = { -1, 1, 0, 0};
int DistanceSum(int N, int *X, int *Y) {
for (int i = 0; i < N; ++i) {
preX.push_back(X[i]);
x.push_back(X[i]);
}
for (int i = 0; i < N; ++i) {
preY.push_back(Y[i]);
y.push_back(Y[i]);
}
if (N <= 2000) {
for (int i = 0 ; i < N ; i++) {
got[make_pair(X[i], Y[i])] = i;
}
for(int i = 0 ; i < N ; i++){
for(int p = 0 ; p < 4 ; p++){
int newX = X[i] + dx[p];
int newY = Y[i] + dy[p];
if(got.find(make_pair(newX,newY)) != got.end()){
adj[i].push_back(got[make_pair(newX,newY)]);
}
}
}
for (int i = 0 ; i < N ; i++) {
queue< int > q;
memset(cost,-1,sizeof cost);
q.push(i);
cost[i] = 0;
while (q.size()) {
int src = q.front();
q.pop();
for (int p = 0 ; p < adj[src].size(); p++) {
int v = adj[src][p];
if(cost[v] == -1){
cost[v] = cost[src] + 1;
q.push(v);
}
}
}
for (int j = i + 1 ; j < N ; j++) {
res += cost[j];
}
}
return res;
}
sort(x.begin(), x.end());
sort(y.begin(), y.end());
sort(preX.begin(), preX.end());
sort(preY.begin(), preY.end());
for (int i = 1 ; i < preX.size(); ++i) {
preX[i] += preX[i - 1];
}
for (int i = 1 ; i < preY.size(); ++i) {
preY[i] += preY[i - 1];
}
for (int i = 0 ; i < N ; i++) {
sum(x, preX, X[i]);
sum(y, preY, Y[i]);
}
return (res / 2) % 1000000000;
}
