#define N 100000
#define MD 1000000000
int abs_(int a) { return a > 0 ? a : -a; }
int ej[N][4], eo[N];
int bfs(int n, int s) {
static int dd[N], qu[N];
int i, head, cnt, sum;
for (i = 0; i < n; i++)
dd[i] = n;
head = cnt = 0;
dd[s] = 0, qu[head + cnt++] = s;
while (cnt) {
int d, o;
i = qu[cnt--, head++], d = dd[i] + 1;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (dd[j] > d)
dd[j] = d, qu[head + cnt++] = j;
}
}
sum = 0;
for (i = s + 1; i < n; i++)
sum = (sum + dd[i]) % MD;
return sum;
}
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
void sort(int *aa, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, a = aa[l + rand_() % (r - l)], tmp;
while (j < k)
if (aa[j] == a)
j++;
else if (aa[j] < a) {
tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
i++, j++;
} else {
k--;
tmp = aa[j], aa[j] = aa[k], aa[k] = tmp;
}
sort(aa, l, i);
l = k;
}
}
int DistanceSum(int n, int *xx, int *yy) {
int i, j, sum;
if (n <= 2000) {
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (abs_(xx[i] - xx[j]) + abs_(yy[i] - yy[j]) == 1)
ej[i][eo[i]++] = j;
sum = 0;
for (i = 0; i < n; i++)
sum = (sum + bfs(n, i)) % MD;
return sum;
} else {
sort(xx, 0, n);
sort(yy, 0, n);
sum = 0;
for (i = 0; i < n; i++)
sum = (sum + (long long) (i - (n - 1 - i)) * xx[i]) % MD;
for (i = 0; i < n; i++)
sum = (sum + (long long) (i - (n - 1 - i)) * yy[i]) % MD;
if (sum < 0)
sum += MD;
}
return sum;
}
