/*
FULL-SCORE SOLUTION
- Time Complexity: O((Q + N) log N)
*/
#include <set>
#include <tuple>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
class value {
public:
long long x; int p1, p2; // value: x + p1 * eps + p2 * eps^2 (eps > 0 is an arbitrary value which is small enough)
value() : x(0), p1(0), p2(0) {}
value(long long x_, int p1_, int p2_) : x(x_), p1(p1_), p2(p2_) {}
bool operator<(const value& v) const { return x != v.x ? x < v.x : (p1 != v.p1 ? p1 < v.p1 : p2 < v.p2); }
bool operator>(const value& v) const { return x != v.x ? x > v.x : (p1 != v.p1 ? p1 > v.p1 : p2 > v.p2); }
value operator+() const { return value(+x, +p1, +p2); }
value operator-() const { return value(-x, -p1, -p2); }
value& operator+=(const value& v) { x += v.x; p1 += v.p1; p2 += v.p2; return *this; }
value& operator-=(const value& v) { x -= v.x; p1 -= v.p1; p2 -= v.p2; return *this; }
value operator+(const value& v) const { return value(*this) += v; }
value operator-(const value& v) const { return value(*this) -= v; }
};
class nearest_info {
public:
int idx; value d1, d2;
nearest_info() : idx(-1), d1(value()), d2(value()) {}
nearest_info(int idx_, const value& d1_, const value& d2_) : idx(idx_), d1(d1_), d2(d2_) {}
};
class segment {
public:
long long a, b, l, r; // y = ax + b (l <= x <= r)
segment() : a(0), b(0), l(0), r(0) {}
segment(long long a_, long long b_, long long l_, long long r_) : a(a_), b(b_), l(l_), r(r_) {}
};
// FUNCTION FOR SOLVING "CONTINUOUS VERSION" OF THE PROBLEM
// - Given N points (X[0], Y[0]), ..., (X[N-1], Y[N-1]) and Q queries with T[0], T[1], ..., T[Q-1]
// - For each query j, answer the following:
// - Consider N squares that, for i = 0, 1, ..., N-1, the lower-left point is at (X[i], Y[i]) and the upper-right point is at (X[i]+T[j], Y[i]+T[j]).
// - Calculate the area of union of these N squares.
vector<long long> area_union(int N, int Q, const vector<long long>& X, const vector<long long>& Y, const vector<long long>& T) {
// step #1. compute nearest colliding square, for each square's corner
vector<value> xp(N), yp(N);
for (int i = 0; i < N; i++) {
xp[i] = value(X[i], i, 0);
yp[i] = value(Y[i], 0, i);
}
vector<vector<nearest_info> > nearest(8, vector<nearest_info>(N)); // d1: distance, d2: "orthogonal" distance
for (int i = 0; i < 8; i++) {
vector<value> xv(N), yv(N);
for (int j = 0; j < N; j++) {
switch (i) {
case 0: xv[j] = +xp[j]; yv[j] = +yp[j]; break;
case 1: xv[j] = +xp[j]; yv[j] = -yp[j]; break;
case 2: xv[j] = -yp[j]; yv[j] = +xp[j]; break;
case 3: xv[j] = -yp[j]; yv[j] = -xp[j]; break;
case 4: xv[j] = -xp[j]; yv[j] = -yp[j]; break;
case 5: xv[j] = -xp[j]; yv[j] = +yp[j]; break;
case 6: xv[j] = +yp[j]; yv[j] = -xp[j]; break;
case 7: xv[j] = +yp[j]; yv[j] = +xp[j]; break;
}
}
vector<int> perm(N);
for (int i = 0; i < N; i++) {
perm[i] = i;
}
sort(perm.begin(), perm.end(), [&](int va, int vb) {
return yv[va] < yv[vb];
});
set<value> s;
for (int j : perm) {
set<value>::iterator it = s.lower_bound(xv[j] - yv[j]);
while (it != s.end() && xv[abs(it->p1)] < xv[j]) {
it = s.erase(it);
}
if (it != s.begin()) {
--it;
nearest[i][j] = nearest_info(abs(it->p1), xv[j] - xv[abs(it->p1)], yv[j] - yv[abs(it->p1)]);
}
s.insert(xv[j] - yv[j]);
}
}
for (int i = 0; i < 8; i += 2) {
int p = vector<int>({ 7, 2, 1, 4, 3, 6, 5, 0 })[i];
for (int j = 0; j < N; j++) {
if (nearest[i][j].idx != -1 && nearest[p][j].idx != -1) {
if (nearest[i][j].d1 > nearest[p][j].d1) {
nearest[i][j] = nearest_info();
}
else {
nearest[p][j] = nearest_info();
}
}
}
}
// step #2. compute "time lapse" of each square's edge
vector<vector<vector<nearest_info> > > timelapse(8, vector<vector<nearest_info> >(N)); // d1: time, d2: distance from another corner
for (int i = 0; i < 8; i++) {
int p1 = vector<int>({ 7, 2, 1, 4, 3, 6, 5, 0 })[i];
int p2 = vector<int>({ 4, 5, 6, 7, 0, 1, 2, 3 })[i];
for (int j = 0; j < N; j++) {
if (nearest[p1][j].idx != -1) {
timelapse[i][j].push_back(nearest_info(nearest[p1][j].idx, nearest[p1][j].d1, nearest[p1][j].d1));
}
if (nearest[p2][j].idx != -1) {
timelapse[i][nearest[p2][j].idx].push_back(nearest_info(j, nearest[p2][j].d1, nearest[p2][j].d2));
}
}
for (int j = 0; j < N; j++) {
sort(timelapse[i][j].begin(), timelapse[i][j].end(), [&](const nearest_info& f1, const nearest_info& f2) {
return f1.d1 < f2.d1;
});
}
}
// step #3. find all crashes & rectangular holes
const long long INF = (3LL << 60);
vector<vector<value> > eliminate(4, vector<value>(N, value(INF, 0, 0)));
for (int i = 0; i < 8; i += 2) {
for (int j = 0; j < N; j++) {
if (!timelapse[i + 0][j].empty() && !timelapse[i + 1][j].empty()) {
nearest_info f0 = timelapse[i + 0][j].back();
nearest_info f1 = timelapse[i + 1][j].back();
value t = f0.d2 + f1.d2;
if ((timelapse[(i + 2) % 8][f0.idx].empty() || timelapse[(i + 2) % 8][f0.idx].back().d1 < t) && timelapse[(i + 3) % 8][f0.idx].back().d1 < t) {
eliminate[((i + 2) % 8) / 2][f0.idx] = min(eliminate[((i + 2) % 8) / 2][f0.idx], t);
}
if ((timelapse[(i + 7) % 8][f1.idx].empty() || timelapse[(i + 7) % 8][f1.idx].back().d1 < t) && timelapse[(i + 6) % 8][f1.idx].back().d1 < t) {
eliminate[((i + 6) % 8) / 2][f1.idx] = min(eliminate[((i + 6) % 8) / 2][f1.idx], t);
}
eliminate[i / 2][j] = min(eliminate[i / 2][j], t);
}
}
}
// step #4. final calculation
vector<segment> seg;
for (int i = 0; i < 8; i += 2) {
for (int j = 0; j < N; j++) {
seg.push_back(segment(1, 0, 0, eliminate[i / 2][j].x));
for (int k = 0; k < 2; k++) {
if (!timelapse[i + k][j].empty()) {
seg.push_back(segment(-1, timelapse[i + k][j][0].d2.x, timelapse[i + k][j][0].d1.x, eliminate[i / 2][j].x));
for (int l = 1; l < timelapse[i + k][j].size(); l++) {
seg.push_back(segment(0, -(timelapse[i + k][j][l - 1].d2 - timelapse[i + k][j][l].d2).x, timelapse[i + k][j][l].d1.x, eliminate[i / 2][j].x));
}
}
}
}
}
vector<long long> tcomp({ 0, INF });
for (segment s : seg) {
if ((s.a != 0 || s.b != 0) && s.l != s.r) {
tcomp.push_back(s.l);
tcomp.push_back(s.r);
}
}
sort(tcomp.begin(), tcomp.end());
tcomp.erase(unique(tcomp.begin(), tcomp.end()), tcomp.end());
vector<long long> polya(tcomp.size()), polyb(tcomp.size()); // y = ax + b
for (segment s : seg) {
if ((s.a != 0 || s.b != 0) && s.l != s.r) {
int pl = lower_bound(tcomp.begin(), tcomp.end(), s.l) - tcomp.begin();
int pr = lower_bound(tcomp.begin(), tcomp.end(), s.r) - tcomp.begin();
polya[pl] += s.a;
polya[pr] -= s.a;
polyb[pl] += s.b;
polyb[pr] -= s.b;
}
}
for (int i = 1; i < tcomp.size(); i++) {
polya[i] += polya[i - 1];
polyb[i] += polyb[i - 1];
}
vector<long long> cum(tcomp.size());
for (int i = 0; i < int(tcomp.size()) - 1; i++) {
long long yl = polya[i] * tcomp[i] + polyb[i];
long long yr = polya[i] * tcomp[i + 1] + polyb[i];
cum[i + 1] = cum[i] + (yl + yr) * (tcomp[i + 1] - tcomp[i]) / 4;
}
vector<long long> answer(Q);
for (int i = 0; i < Q; i++) {
int pos = lower_bound(tcomp.begin(), tcomp.end(), T[i] + 1) - tcomp.begin() - 1;
long long yl = polya[pos] * tcomp[pos] + polyb[pos];
long long yt = polya[pos] * T[i] + polyb[pos];
answer[i] = cum[pos] + (yl + yt) * (T[i] - tcomp[pos]) / 4;
}
return answer;
}
// FUNCTION FOR SOLVING THE MAIN PROBLEM
vector<long long> solve(int N, int Q, const vector<long long>& X, const vector<long long>& Y, const vector<long long>& T) {
auto half = [&](long long x) {
return (x >= 0 ? x / 2 : -((-x + 1) / 2));
};
vector<long long> xa, ya, xb, yb;
for (int i = 0; i < N; i++) {
if ((X[i] + Y[i]) % 2 == 0) {
xa.push_back((X[i] + Y[i] + 0) / 2); ya.push_back((X[i] - Y[i] + 0) / 2);
xa.push_back((X[i] + Y[i] + 0) / 2); ya.push_back((X[i] - Y[i] + 2) / 2);
xa.push_back((X[i] + Y[i] + 2) / 2); ya.push_back((X[i] - Y[i] + 0) / 2);
xa.push_back((X[i] + Y[i] + 2) / 2); ya.push_back((X[i] - Y[i] + 2) / 2);
xb.push_back((X[i] + Y[i] + 2) / 2); yb.push_back((X[i] - Y[i] + 2) / 2);
}
else {
xa.push_back((X[i] + Y[i] + 1) / 2); ya.push_back((X[i] - Y[i] + 1) / 2);
xb.push_back((X[i] + Y[i] + 1) / 2); yb.push_back((X[i] - Y[i] + 1) / 2);
xb.push_back((X[i] + Y[i] + 1) / 2); yb.push_back((X[i] - Y[i] + 3) / 2);
xb.push_back((X[i] + Y[i] + 3) / 2); yb.push_back((X[i] - Y[i] + 1) / 2);
xb.push_back((X[i] + Y[i] + 3) / 2); yb.push_back((X[i] - Y[i] + 3) / 2);
}
}
vector<long long> T2(Q * 2);
for (int i = 0; i < Q; i++) {
T2[i * 2 + 0] = T[i];
T2[i * 2 + 1] = (T[i] >= 1 ? T[i] - 1 : 0);
}
vector<long long> resa = area_union(xa.size(), Q * 2, xa, ya, T2);
vector<long long> resb = area_union(xb.size(), Q * 2, xb, yb, T2);
vector<long long> answer(Q, 0);
for (int i = 0; i < Q; i++) {
if (T[i] == 0) {
answer[i] = N;
}
else {
answer[i] += resa[2 * i + 0] - (T[i] >= 2 ? resa[2 * i + 1] : 0);
answer[i] += resb[2 * i + 0] - (T[i] >= 2 ? resb[2 * i + 1] : 0);
if (T[i] == 1) {
answer[i] -= N;
}
}
}
return answer;
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
vector<long long> X(N), Y(N), T(Q);
for (int i = 0; i < N; i++) {
cin >> X[i] >> Y[i];
}
for (int i = 0; i < Q; i++) {
cin >> T[i];
}
vector<long long> answer = solve(N, Q, X, Y, T);
for (int i = 0; i < Q; i++) {
cout << answer[i] << '\n';
}
return 0;
}
