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.