#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;
}
int DistanceSum(int n, int *xx, int *yy) {
int i, j, sum;
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;
}
