#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100000
#define N_ 2000
#define Q 500000
#define X 2000
#define T 1000
#define INF 0x7fffffff
int abs_(int a) { return a > 0 ? a : -a; }
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int xx[N], yy[N], uu[N], vv[N]; int tt_[N], n;
int tt[Q]; long long ans[Q]; int q;
int *ww;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = ww[ii[j]] != ww[i_] ? (ww[ii[j]] < ww[i_] ? -1 : 1) : (xx[ii[j]] != xx[i_] ? (xx[ii[j]] < xx[i_] ? -1 : 1) : 0);
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
void solve2() {
static int dd[X * 2 + 1][X * 2 + 1], nn[T + 1];
int h, i, x, y;
for (x = 0; x <= X * 2; x++)
for (y = 0; y <= X * 2; y++)
dd[x][y] = T + 1;
for (i = 0; i < n; i++)
dd[X + xx[i]][X + yy[i]] = 0;
for (x = 0; x <= X * 2; x++) {
for (y = 1; y <= X * 2; y++)
dd[x][y] = min(dd[x][y], dd[x][y - 1] + 1);
for (y = X * 2 - 1; y >= 0; y--)
dd[x][y] = min(dd[x][y], dd[x][y + 1] + 1);
}
for (y = 0; y <= X * 2; y++) {
for (x = 1; x <= X * 2; x++)
dd[x][y] = min(dd[x][y], dd[x - 1][y] + 1);
for (x = X * 2 - 1; x >= 0; x--)
dd[x][y] = min(dd[x][y], dd[x + 1][y] + 1);
}
memset(nn, 0, (T + 1) * sizeof *nn);
for (x = 0; x <= X * 2; x++)
for (y = 0; y <= X * 2; y++)
if (dd[x][y] <= T)
nn[dd[x][y]]++;
for (h = 0; h < q; h++)
ans[h] = nn[tt[h]];
}
void solve4() {
static int ii[N];
int h, i, i_, a, t;
long long b;
for (i = 0; i < n; i++)
ii[i] = i;
ww = xx, sort(ii, 0, n);
for (i = 0; i + 1 < n; i++) {
tt_[i] = xx[ii[i + 1]] - xx[ii[i]];
ii[i] = i;
}
ww = tt_, sort(ii, 0, n - 1);
i = 0, a = n * 4, b = 0;
for (h = 0; h < q; h++) {
t = tt[h];
if (t == 0) {
ans[h] = n;
continue;
}
while (i < n - 1 && tt_[i_ = ii[i]] < t) {
a -= 4, b += tt_[i_] * 2;
i++;
}
ans[h] = 0;
while (i < n - 1 && tt_[i_ = ii[i]] == t) {
ans[h] += t - 1;
a -= 4, b += tt_[i_] * 2;
i++;
}
ans[h] += (long long) a * t + b;
}
}
int xx_[N], yy_[N];
void compress(int *xx, int *xx_, int n) {
static int ii[N];
int i, x;
for (i = 0; i < n; i++)
ii[i] = i;
ww = xx, sort(ii, 0, n);
for (i = 0, x = 0; i < n; i++)
xx_[ii[i]] = i + 1 == n || xx[ii[i + 1]] != xx[ii[i]] ? x++ : x;
}
int *ej[N], eo[N];
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
int ft[N];
int min_(int i, int j) {
return j == -1 || i != -1 && (vv[i] < vv[j] || vv[i] == vv[j] && i < j) ? i : j;
}
void update(int i, int n, int x) {
while (i < n) {
ft[i] = min_(ft[i], x);
i |= i + 1;
}
}
int query(int i) {
int x = -1;
while (i >= 0) {
x = min_(x, ft[i]);
i &= i + 1, i--;
}
return x;
}
int aa[Q + 1]; long long bb[Q + 1];
void add(int t, int a, long long b) {
int lower = -1, upper = q;
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (tt[h] >= t)
upper = h;
else
lower = h;
}
aa[upper] += a, bb[upper] += b;
}
void solve6() {
static int ii[N], qu[N], jjl[N * 4], jjr[N * 4];
int cnt, h, i, i_, j, j_, jl, jr, r, o, t, t_, tmp;
long long u, u_, ul, ur;
for (i = 0; i < n; i++)
uu[i] = xx[i] - yy[i], vv[i] = xx[i] + yy[i];
memset(aa, 0, (q + 1) * sizeof *aa), memset(bb, 0, (q + 1) * sizeof *bb);
for (i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
compress(xx, xx_, n), compress(yy, yy_, n);
for (r = 0; r < 4; r++) {
for (i = 0; i < n; i++)
ii[i] = i;
ww = uu, sort(ii, 0, n);
memset(ft, -1, n * sizeof *ft);
for (i = 0; i < n; i = j) {
j = i + 1;
while (j < n && uu[ii[j]] == uu[ii[i]])
j++;
for (h = i; h < j; h++) {
i_ = ii[h], j_ = query(n - 1 - xx_[i_]);
if (j_ != -1)
append(i_, j_), append(j_, i_);
update(n - 1 - xx_[i_], n, i_);
}
cnt = 0;
for (h = i; h < j; h++) {
i_ = ii[h];
while (cnt && qu[cnt - 1] > i_)
cnt--;
if (cnt) {
j_ = qu[cnt - 1];
append(i_, j_), append(j_, i_);
}
qu[cnt++] = i_;
}
}
memset(ft, -1, n * sizeof *ft);
for (j = n; j > 0; j = i) {
i = j - 1;
while (i > 0 && uu[ii[i - 1]] == uu[ii[j - 1]])
i--;
for (h = i; h < j; h++) {
i_ = ii[h], j_ = query(n - 1 - yy_[i_]);
if (j_ != -1)
append(i_, j_), append(j_, i_);
update(n - 1 - yy_[i_], n, i_);
}
}
for (i = 0; i < n; i++) {
tmp = xx[i], xx[i] = -yy[i], yy[i] = tmp;
tmp = xx_[i], xx_[i] = n - 1 - yy_[i], yy_[i] = tmp;
tmp = uu[i], uu[i] = -vv[i], vv[i] = tmp;
}
}
for (i = 0; i < n; i++) {
for (o = 0; o < eo[i]; o++) {
j = ej[i][o];
tt_[j] = ((long long) abs_(xx[j] - xx[i]) + abs_(yy[j] - yy[i]) + (i < j ? 2 : 1)) / 2;
}
ww = tt_, sort(ej[i], 0, eo[i]);
}
cnt = 0;
for (r = 0; r < 4; r++) {
for (i = 0; i < n; i++) {
u = uu[i], ul = -INF, jl = -1, ur = INF, jr = -1, t_ = -1;
for (o = 0; o < eo[i]; o++) {
j = ej[i][o], t = ((long long) abs_(xx[j] - xx[i]) + abs_(yy[j] - yy[i]) + (i < j ? 2 : 1)) / 2;
if (vv[j] < vv[i] || vv[j] == vv[i] && j > i)
continue;
if (ul != -INF && ur != INF && ul + t > ur - t + 1 && t != t_)
break;
t_ = t;
if (uu[j] < u) {
u_ = uu[j] + (i < j ? 0 : 1);
if (ul == -INF)
ul = u_, jl = j;
else {
ul = max(ul, u_);
if (uu[jl] < uu[j] || uu[jl] == uu[j] && jl > j)
jl = j;
}
} else {
u_ = uu[j] - (i < j ? 0 : 1);
if (ur == INF)
ur = u_, jr = j;
else {
ur = min(ur, u_);
if (uu[jr] > uu[j] || uu[jr] == uu[j] && jr > j)
jr = j;
}
}
}
if (jl != -1 && jr != -1)
jjl[cnt] = jl, jjr[cnt] = jr, cnt++;
}
for (i = 0; i < n; i++) {
tmp = xx[i], xx[i] = -yy[i], yy[i] = tmp;
tmp = uu[i], uu[i] = -vv[i], vv[i] = tmp;
}
}
for (h = 0; h < cnt; h++) {
jl = jjl[h], jr = jjr[h];
append(jl, jr), append(jr, jl);
}
for (i = 0; i < n; i++) {
for (o = 0; o < eo[i]; o++) {
j = ej[i][o];
tt_[j] = ((long long) abs_(xx[j] - xx[i]) + abs_(yy[j] - yy[i]) + (i < j ? 2 : 1)) / 2;
}
ww = tt_, sort(ej[i], 0, eo[i]);
}
for (r = 0; r < 4; r++) {
for (i = 0; i < n; i++) {
add(0, 1, 0);
u = uu[i], ul = -INF, ur = INF, t = INF;
for (o = 0; o <= eo[i]; o++) {
if (o == eo[i]) {
t = ul != -INF && ur != INF ? (ur - ul) / 2 + 1 : INF;
break;
}
j = ej[i][o], t = ((long long) abs_(xx[j] - xx[i]) + abs_(yy[j] - yy[i]) + (i < j ? 2 : 1)) / 2;
if (vv[j] < vv[i] || vv[j] == vv[i] && j > i)
continue;
if (ul != -INF && ur != INF && ul + t > ur - t) {
t = (ur - ul) / 2 + 1;
break;
}
if (uu[j] < u) {
u_ = uu[j] + (i < j ? 0 : 1);
if (ul == -INF)
add(t, -1, (u - u_) / 2), ul = u_;
else if (ul < u_)
add(t, 0, (u - u_) / 2 - (u - ul) / 2), ul = u_;
} else {
u_ = uu[j] - (i < j ? 0 : 1);
if (ur == INF)
add(t, -1, (u_ - u + 2) / 2), ur = u_;
else if (ur > u_)
add(t, 0, (u_ - u + 2) / 2 - (ur - u + 2) / 2), ur = u_;
}
if (ul != -INF && ur != INF && ul + t > ur - t)
break;
}
if (t != INF)
add(t, 1, -((u - ul) / 2 + (ur - u + 2) / 2));
}
for (i = 0; i < n; i++) {
tmp = xx[i], xx[i] = -yy[i], yy[i] = tmp;
tmp = uu[i], uu[i] = -vv[i], vv[i] = tmp;
}
}
for (h = 1; h < q; h++)
aa[h] += aa[h - 1], bb[h] += bb[h - 1];
for (h = 0; h < q; h++)
ans[h] = tt[h] == 0 ? n : (long long) aa[h] * tt[h] + bb[h];
}
void test() {
static long long ans_[Q];
int h;
solve2(), memcpy(ans_, ans, q * sizeof *ans), solve6();
for (h = 0; h < q; h++)
if (ans[h] != ans_[h]) {
printf("wrong answer on query %d: expected %lld, found %lld\n", h + 1, ans_[h], ans[h]);
exit(0);
}
}
void stress() {
int t, h, i, j;
for (t = 1; t <= T; t++) {
printf("running on test %d...\n", t);
generate:
n = 10, q = T + 1;
for (i = 0; i < n; i++)
xx[i] = rand_() % 21 - 10, yy[i] = rand_() % 21 - 10;
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
if (xx[j] == xx[i] && yy[j] == yy[i])
goto generate;
for (h = 0; h < q; h++)
tt[h] = h;
test();
}
printf("AC\n");
}
int main() {
int h, i, subtask;
scanf("%d%d", &n, &q);
for (i = 0; i < n; i++)
scanf("%d%d", &xx[i], &yy[i]);
for (h = 0; h < q; h++)
scanf("%d", &tt[h]);
#if 0
stress();
return 0;
#endif
if (n <= N_)
subtask = 6;
else {
subtask = 4;
for (i = 0; i < n; i++)
if (xx[i] != yy[i]) {
subtask = 2;
break;
}
}
if (subtask == 2)
solve2();
else if (subtask == 4)
solve4();
else if (subtask == 6)
solve6();
for (h = 0; h < q; h++)
printf("%lld\n", ans[h]);
return 0;
}
