#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; }