P9513 [JOI Open 2023] Cell Automaton / Cell Automaton

**Translated from [JOI Open 2023](https://contests.ioi-jp.org/open-2023/index.html) T2 「[セルオートマトン](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/cell/2023-open-cell-statement.pdf) / [Cell Automaton](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/cell/2023-open-cell-statement-en.pdf)」。**

We have a sufficiently large 2D grid, tiled with square cells from top to bottom and from left to right. One cell is the origin. Let $(x,y)$ denote the cell reached by moving $x$ cells to the right from the origin, and then moving $y$ cells upward. Here, moving $a$ cells to the left means moving $-a$ cells to the right. Similarly, moving $a$ cells downward means moving $-a$ cells upward. At time $0$, the cells $(X_1,Y_1),(X_2,Y_2),\ldots,(X_N,Y_N)$ are black, and all other cells are white. For $t=0,1,2,\ldots$, based on the colors of the cells at time $t$, the colors at time $t+1$ are determined as follows: - If a cell is black at time $t$, then at time $t+1$ this cell becomes gray. - If a cell is gray at time $t$, then at time $t+1$ this cell becomes white. - If a cell is white at time $t$, and among its four adjacent cells (i.e., the four cells sharing an edge with it) at least one is black at time $t$, then at time $t+1$ this cell becomes black. Otherwise, it remains white at time $t+1$. You have $Q$ queries. For the $j$-th query, you should answer how many black cells there are at time $T_j$. Given the initial cell colors at time $0$ and the queries, write a program to answer the queries.

The first line contains two integers $N,Q$. The next $N$ lines each contain two integers $X_i,Y_i$. The next $Q$ lines each contain one integer $T_j$.

Output $Q$ lines, each containing one integer, representing the number of black cells at time $T_j$.

**[Sample Explanation #1]** The figure below shows the state of the cells at time $0$. Since there are $2$ black cells, the answer to the first query is $2$.  The figure below shows the state of the cells at time $1$. Since there are $8$ black cells, the answer to the second query is $8$.  The figure below shows the state of the cells at time $2$. Since there are $12$ black cells, the answer to the third query is $12$.  This sample satisfies the constraints of subtasks $1,2,6,7$. **[Sample Explanation #2]** This sample satisfies the constraints of subtasks $1,2,4,6,7$. **[Sample Explanation #3]** This sample satisfies the constraints of subtasks $1,2,6,7$. **[Constraints]** For all testdata, the following hold: - $1\le N\le 10^5$ - $1\le Q\le 5\times 10^5$ - $|X_i|,|Y_i|\le 10^9$ - $(X_i,Y_i)\neq (X_j,Y_j)\ (1\le i < j\le N)$ - $0\le T_j\le 10^9$ - $T_j