#include <stdio.h>
#define N 100000
#define SMALL 2000
#define M (SMALL * 15)
#define MV (SMALL * 4)
#define ME M
#define M_ (MV + ME * 2)
#define M1 (M + SMALL * 4)
#define X 2000
#define T 1000
#define INF 0x3f3f3f3f3f3f3f3f
int min(int a, int b) { return a < b ? a : b; }
int abs_(int a) { return a > 0 ? a : -a; }
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int xx[N], yy[N], n; long long uu[N], vv[N];
int ej[SMALL][SMALL], eo[SMALL];
int r;
long long tt[M]; int aa[M]; long long bb[M]; int hh[M], m;
int ttv[MV], xxv[MV], yyv[MV], mv;
int tte[2][ME], xxe[2][ME * 2], yye[2][ME], mme[2];
int tt_[M_], xx_[M_], yy_[M_], ww_[M_], hh_[M_], m_;
int tt1[M1]; long long cc1[M1]; int hh1[M1], m1;
int compare_x(int i, int j) {
return xx[i] == xx[j] ? 0 : (xx[i] < xx[j] ? -1 : 1);
}
int compare_t1(int i, int j) {
return tt1[i] == tt1[j] ? 0 : (tt1[i] < tt1[j] ? -1 : 1);
}
long long dist(int i, int j) {
return (long long) abs_(xx[j] - xx[i]) + abs_(yy[j] - yy[i]);
}
int i1;
int compare_d(int i, int j) {
long long di = dist(i1, i), dj = dist(i1, j);
return di == dj ? 0 : di < dj ? -1 : 1;
}
int compare_t(int h1, int h2) {
return tt[h1] == tt[h2] ? 0 : (tt[h1] < tt[h2] ? -1 : 1);
}
int compare_t_(int h1, int h2) {
return tt_[h1] == tt_[h2] ? 0 : (tt_[h1] < tt_[h2] ? -1 : 1);
}
int compare_yxw(int h1, int h2) {
if (yy_[h1] != yy_[h2])
return yy_[h1] < yy_[h2] ? -1 : 1;
if (xx_[h1] != xx_[h2])
return xx_[h1] < xx_[h2] ? -1 : 1;
if (ww_[h1] != ww_[h2])
return ww_[h1] < ww_[h2] ? -1 : 1;
return 0;
}
int compare_xyw(int h1, int h2) {
if (xx_[h1] != xx_[h2])
return xx_[h1] < xx_[h2] ? -1 : 1;
if (yy_[h1] != yy_[h2])
return yy_[h1] < yy_[h2] ? -1 : 1;
if (ww_[h1] != ww_[h2])
return ww_[h1] < ww_[h2] ? -1 : 1;
return 0;
}
int (*compare)(int, int);
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 = compare(ii[j], i_);
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 get_neighbors() {
int i, j;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (j != i)
ej[i][eo[i]++] = j;
for (i = 0; i < n; i++)
compare = compare_d, i1 = i, sort(ej[i], 0, eo[i]);
}
void add_func(long long t, int a, long long b) {
tt[m] = t, aa[m] = a, bb[m] = b, m++;
}
void add_vertex(int t, int x, int y) {
if ((x + y) % 2 != 0)
return;
if (r == 0)
ttv[mv] = t, xxv[mv] = x, yyv[mv] = y, mv++;
else if (r == 1)
ttv[mv] = t, xxv[mv] = y, yyv[mv] = -x, mv++;
else if (r == 2)
ttv[mv] = t, xxv[mv] = -x, yyv[mv] = -y, mv++;
else
ttv[mv] = t, xxv[mv] = -y, yyv[mv] = x, mv++;
}
void add_edge(int t, int x1, int x2, int y) {
if ((x1 + y) % 2 != 0)
x1--;
if ((x2 + y) % 2 != 0)
x2++;
if (x1 >= x2)
return;
if (r == 0) {
tte[0][mme[0]] = t;
xxe[0][mme[0] << 1 | 0] = x1, xxe[0][mme[0] << 1 | 1] = x2;
yye[0][mme[0]] = y;
mme[0]++;
} else if (r == 1) {
tte[1][mme[1]] = t;
xxe[1][mme[1] << 1 | 0] = -x2, xxe[1][mme[1] << 1 | 1] = -x1;
yye[1][mme[1]] = y;
mme[1]++;
} else if (r == 2) {
tte[0][mme[0]] = t;
xxe[0][mme[0] << 1 | 0] = -x2, xxe[0][mme[0] << 1 | 1] = -x1;
yye[0][mme[0]] = -y;
mme[0]++;
} else {
tte[1][mme[1]] = t;
xxe[1][mme[1] << 1 | 0] = x1, xxe[1][mme[1] << 1 | 1] = x2;
yye[1][mme[1]] = -y;
mme[1]++;
}
}
long long count_points(int *hh, int m) {
long long c;
int m_, h, h_, d, x_, y_;
c = 0;
compare = compare_yxw, sort(hh, 0, m);
m_ = 0, d = 0, x_ = 0;
for (h = 0; h < m; h++) {
h_ = hh[h];
if (ww_[h_] == 1) {
hh[m_++] = h_;
if (d++ == 0)
x_ = xx_[h_];
} else if (ww_[h_] == -1) {
hh[m_++] = h_;
if (--d == 0)
c += ((long long) xx_[h_] - x_) / 2 - 1;
} else if (ww_[h_] == 0)
if (d == 0)
hh[m_++] = h_;
}
m = m_;
compare = compare_xyw, sort(hh, 0, m);
m_ = 0, d = 0, y_ = 0;
for (h = 0; h < m; h++) {
h_ = hh[h];
if (ww_[h_] == 2) {
if (d++ == 0)
y_ = yy_[h_];
} else if (ww_[h_] == -2) {
if (--d == 0)
c += ((long long) yy_[h_] - y_) / 2 - 1;
} else if (ww_[h_] == 0)
if (d == 0)
hh[m_++] = h_;
}
m = m_;
for (h = 0; h < m; h++)
if (h == 0 || xx_[hh[h]] != xx_[hh[h - 1]] || yy_[hh[h]] != yy_[hh[h - 1]])
c++;
return c;
}
void get_events() {
int h, h_, i, j, o, ol, or, tmp, corner;
long long t, ul, ur;
for (r = 0; r < 4; r++) {
for (i = 0; i < n; i++)
uu[i] = xx[i] - yy[i], vv[i] = xx[i] + yy[i];
for (i = 0; i < n; i++) {
ul = -INF, ur = INF;
for (ol = 0; ol < eo[i]; ol++) {
j = ej[i][ol], t = dist(i, j);
or = ol + 1;
while (or < eo[i] && dist(i, ej[i][or]) == t)
or++;
corner = 0;
for (o = ol; o < or; o++) {
j = ej[i][o];
if (ul != -INF && ur != INF && t >= ur - ul) {
add_func(ur - ul, 1, ul - ur);
if ((ur - ul) % 2 == 0)
add_vertex((ur - ul) / 2, (ul + ur) / 2, vv[i] + (ur - ul) / 2);
goto out;
}
if (vv[i] <= vv[j] && xx[i] > xx[j]) {
if (ul == -INF)
add_func(t, -1, t), ul = uu[j];
} else if (yy[i] >= yy[j] && vv[i] < vv[j]) {
if (ur == INF)
add_func(t, -1, t), ur = uu[j];
if (corner == 0 && i < j && yy[i] == yy[j])
corner = 1;
else
corner = -1;
} else if (xx[i] <= xx[j] && uu[i] > uu[j]) {
if (ul == -INF) {
if (ur != INF && t >= ur - uu[j]) {
add_func(t, 0, uu[i] - ur);
if (t % 2 == 0) {
add_vertex(t / 2, ur - t / 2, vv[i] + t / 2);
add_edge(t / 2, uu[i] - t / 2, ur - t / 2, vv[i] + t / 2);
}
goto out;
} else {
add_func(t, -1, uu[i] - uu[j]);
if (t % 2 == 0)
add_edge(t / 2, uu[i] - t / 2, uu[j] + t / 2, vv[i] + t / 2);
ul = uu[j];
}
} else {
if (ur != INF && t >= ur - uu[j]) {
add_func(t, 1, ul - ur);
if (t % 2 == 0) {
add_vertex(t / 2, ur - t / 2, vv[i] + t / 2);
add_edge(t / 2, ul + t / 2, ur - t / 2, vv[i] + t / 2);
}
goto out;
} else if (ul < uu[j]) {
add_func(t, 0, ul - uu[j]);
if (t % 2 == 0)
add_edge(t / 2, ul + t / 2, uu[j] + t / 2, vv[i] + t / 2);
ul = uu[j];
}
}
} else if (uu[i] <= uu[j] && yy[i] < yy[j]) {
if (ur == INF) {
if (ul != -INF && t >= uu[j] - ul) {
add_func(t, 0, ul - uu[i]);
if (t % 2 == 0) {
add_vertex(t / 2, ul + t / 2, vv[i] + t / 2);
add_edge(t / 2, ul + t / 2, uu[i] + t / 2, vv[i] + t / 2);
}
goto out;
} else {
add_func(t, -1, uu[j] - uu[i]);
if (t % 2 == 0)
add_edge(t / 2, uu[j] - t / 2, uu[i] + t / 2, vv[i] + t / 2);
ur = uu[j];
}
} else {
if (ul != -INF && t >= uu[j] - ul) {
add_func(t, 1, ul - ur);
if (t % 2 == 0) {
add_vertex(t / 2, ul + t / 2, vv[i] + t / 2);
add_edge(t / 2, ul + t / 2, ur - t / 2, vv[i] + t / 2);
}
goto out;
} else if (ur > uu[j]) {
add_func(t, 0, uu[j] - ur);
if (t % 2 == 0)
add_edge(t / 2, uu[j] - t / 2, ur - t / 2, vv[i] + t / 2);
ur = uu[j];
}
}
}
}
if (t % 2 == 0 && corner == 1 && ul < uu[i] + t && ur == uu[i] + t)
tt1[m1] = t / 2, cc1[m1] = -1, m1++;
}
out:
if (o == eo[i] && ul != -INF && ur != INF) {
add_func(ur - ul, 1, ul - ur);
if ((ur - ul) % 2 == 0)
add_vertex((ur - ul) / 2, (ul + ur) / 2, vv[i] + (ur - ul) / 2);
}
}
for (i = 0; i < n; i++)
tmp = xx[i], xx[i] = -yy[i], yy[i] = tmp;
}
for (h = 0; h < m; h++)
hh[h] = h;
compare = compare_t, sort(hh, 0, m);
for (h = 0; h < mv; h++)
tt_[m_] = ttv[h], xx_[m_] = xxv[h], yy_[m_] = yyv[h], ww_[m_] = 0, m_++;
for (h = 0; h < mme[0]; h++)
if (xxe[0][h << 1 | 0] != xxe[0][h << 1 | 1]) {
tt_[m_] = tte[0][h], xx_[m_] = xxe[0][h << 1 | 0], yy_[m_] = yye[0][h], ww_[m_] = 1, m_++;
tt_[m_] = tte[0][h], xx_[m_] = xxe[0][h << 1 | 1], yy_[m_] = yye[0][h], ww_[m_] = -1, m_++;
}
for (h = 0; h < mme[1]; h++)
if (xxe[1][h << 1 | 0] != xxe[1][h << 1 | 1]) {
tt_[m_] = tte[1][h], xx_[m_] = yye[1][h], yy_[m_] = xxe[1][h << 1 | 0], ww_[m_] = 2, m_++;
tt_[m_] = tte[1][h], xx_[m_] = yye[1][h], yy_[m_] = xxe[1][h << 1 | 1], ww_[m_] = -2, m_++;
}
for (h = 0; h < m_; h++)
hh_[h] = h;
compare = compare_t_, sort(hh_, 0, m_);
for (h = 0; h < m_; h = h_) {
t = tt_[hh_[h]], h_ = h + 1;
while (h_ < m_ && tt_[hh_[h_]] == t)
h_++;
tt1[m1] = t, cc1[m1] = count_points(hh_ + h, h_ - h), m1++;
}
for (h = 0; h < m1; h++)
hh1[h] = h;
compare = compare_t1, sort(hh1, 0, m1);
}
int main() {
int q, subtask, h, h1, i, x, y, a;
long long t, b, ans;
scanf("%d%d", &n, &q);
for (i = 0; i < n; i++)
scanf("%d%d", &xx[i], &yy[i]);
if (n <= 2000)
subtask = 6;
else {
subtask = 4;
for (i = 0; i < n; i++)
if (xx[i] != yy[i]) {
subtask = 2;
break;
}
}
if (subtask == 2) {
static int dd[X * 2 + 1][X * 2 + 1], nn[T + 1];
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);
}
for (x = 0; x <= X * 2; x++)
for (y = 0; y <= X * 2; y++)
if (dd[x][y] <= T)
nn[dd[x][y]]++;
while (q--) {
scanf("%lld", &t);
printf("%d\n", nn[t]);
}
} else if (subtask == 4) {
static int ii[N];
int i_;
for (i = 0; i < n; i++)
ii[i] = i;
compare = compare_x, sort(ii, 0, n);
for (i = 0; i + 1 < n; i++) {
tt1[i] = xx[ii[i + 1]] - xx[ii[i]];
ii[i] = i;
}
compare = compare_t1, sort(ii, 0, n - 1);
i = 0, a = n * 4, b = 0;
while (q--) {
long long ans;
scanf("%lld", &t);
if (t == 0)
printf("%d\n", n);
else {
while (i < n - 1 && tt1[i_ = ii[i]] < t) {
a -= 4, b += (long long) tt1[i_] * 2;
i++;
}
ans = 0;
while (i < n - 1 && tt1[i_ = ii[i]] == t) {
ans += t - 1;
a -= 4, b += (long long) tt1[i_] * 2;
i++;
}
ans += a * t + b;
printf("%lld\n", ans);
}
}
} else {
get_neighbors();
get_events();
h = 0, h1 = 0, a = n * 4, b = 0;
while (q--) {
scanf("%lld", &t);
if (t == 0)
ans = n;
else {
while (h < m && tt[hh[h]] <= t * 2)
a += aa[hh[h]], b += bb[hh[h]], h++;
while (h1 < m1 && tt1[h1] < t)
h1++;
ans = (a * t * 2 + b) / 2;
while (h1 < m1 && tt1[h1] == t)
ans += cc1[h1], h1++;
}
printf("%lld\n", ans);
}
}
return 0;
}
