28442번 - Cell Automaton 서브태스크다국어

We have a sufficiently large $2$-dimensional grid of cells. The grid is paved with square cells from the top to the bottom and from the left to the right.

There is a cell, which is the origin of the coordinates. Let $(x, y)$ denote the cell one arrives at when one moves from the origin to the right direction for the distance of $x$ cells and to the upward direction for the distance of $y$ cells. Here, the left direction for the distance of $a$ cells means the right direction for the distance of $-a$ cells. Similarly, the downward direction for the distance of $a$ cells means the upward direction for the distance of $-a$ cells.

At time $0$, the cells $(X_1, Y_1), (X_2, Y_2), \dots , (X_N, Y_N)$ are black, and all of the other cells are white.

For $t = 0, 1, 2, \dots$, the colors of the cells at time $t + 1$ are determined by the colors of the cells at time $t$ in the following way.

• If a cell is black at time $t$, then the cell becomes gray at time $t + 1$.
• If a cell is gray at time $t$, then the cell becomes white at time $t + 1$.
• A cell which is white at time $t$ becomes black at time $t + 1$ if at least one of the $4$ adjacent cells (i.e. the $4$ cells which share the edges) is black at time $t$. Otherwise, it remains white at time $t + 1$.

You have $Q$ queries. For the $j$-th ($1 ≤ j ≤ Q$) query, you should answer the number of black cells at time $T_j$.

Write a program which, given the information of the colors of the cells at time 0 and queries, answers the queries.

Read the following data from the standard input.

$N$ $Q$

$X_1$ $Y_1$

$X_2$ $Y_2$

$\vdots$

$X_N$ $Y_N$

$T_1$

$T_2$

$\vdots$

$T_Q$

Write $Q$ lines to the standard output. The $j$-th line should contain the number of black cells at time $T_j$.

• $1 ≤ N ≤ 100\,000$.
• $1 ≤ Q ≤ 500\,000$.
• $|X_i | ≤ 10^9$ ($1 ≤ i ≤ N$).
• $|Y_i | ≤ 10^9$ ($1 ≤ i ≤ N$).
• $(X_i , Y_i) \ne (X_j , Y_j)$ ($1 ≤ i < j ≤ N$).
• $0 ≤ T_j ≤ 10^9$ ($1 ≤ j ≤ Q$).
• $T_j < T_{j+1}$ ($1 ≤ j ≤ Q - 1$).
• Given values are all integers.