Grid Color Evolution

We are given an infinite 2D grid fully tiled with square cells. One special cell is the origin. We denote a cell by ((x,y)), which is reached by moving (x) cells to the right and (y) cells upward from the origin (note that moving left or down is indicated by negative values of (x) or (y), respectively).

At time (t=0), the cells at positions ((X_1,Y_1), (X_2,Y_2), \ldots, (X_N,Y_N)) are black and all other cells are white.

For each time step (t=0,1,2,\ldots), the colors evolve as follows:

• If a cell is black at time \(t\), then at time \(t+1\) it becomes gray.
• If a cell is gray at time \(t\), then it becomes white at time \(t+1\>.
• If a cell is white at time \(t\) and at least one of its four edge‐adjacent neighbors (up, down, left, right) is black at time \(t\), then the cell becomes black at time \(t+1\); otherwise, it remains white.

You are given \(Q\) queries. For each query you are to determine the number of black cells at time \(T_j\).

inputFormat

The first line contains two integers (N) and (Q) ((1 \le N, Q\le) reasonable limits). The next (N) lines each contain two integers (X_i) and (Y_i) indicating that cell ((X_i,Y_i)) is initially black at time 0. Each of the following (Q) lines contains one integer (T_j) representing a query time.

outputFormat

For each query, output a single integer on a new line representing the number of black cells at time (T_j).

sample

1 3
0 0
0
1
2

1
4
8

</p>