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),\ldots, (X_N, Y_N)~ are black, and all of the other cells are white. For ~t = 0, 1, 2, \ldots~, 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 \le j \le 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.

Input Specification

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~

Output Specification

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

Input Constraints

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

Subtasks

1. (4 points) ~|X_i| \le 50~ (~1 \le i \le N~), ~|Y_i| \le 50~ (~1 \le i \le N~), ~T_j \le 50~ (~1 \le j \le Q~).
2. (12 points) ~|X_i| \le 1\ 000~ (~1 \le i \le N~), ~|Y_i| \le 1\ 000~ (~1 \le i \le N~), ~T_j \le 1\ 000~ (~1 \le j \le Q~).
3. (8 points) ~X_i = Y_i~ (~1 \le i \le N~), ~Q = 1~.
4. (8 points) ~X_i = Y_i~ (~1 \le i \le N~).
5. (17 points) ~N \le 2\ 000~, ~Q = 1~.
6. (25 points) ~N \le 2\ 000~.
7. (26 points) No additional constraints.

Sample Input 1

2 3
0 2
1 0
0
1
2

Sample Output 1

2
8
12

Explanation for Sample 1

The following figure shows the colors of the cells at time ~0~. Since there are ~2~ black cells, the answer to the first query is ~2~.

The following figure shows the colors of the cells at time ~1~. Since there are ~8~ black cells, the answer to the second query is ~8~.

The following figure shows the colors of the cells at time ~2~. Since there are ~12~ black cells, the answer to the third query is ~12~.

This sample input satisfies the constraints of Subtasks ~1, 2, 6, 7~.

Sample Input 2

3 5
0 0
2 2
5 5
0
1
2
3
4

Sample Output 2

3
12
21
24
26

Explanation for Sample 2

This sample input satisfies the constraints of Subtasks ~1, 2, 4, 6, 7~.

Sample Input 3

4 10
-3 -3
3 3
-4 4
4 -4
0
1
2
3
4
5
6
7
8
9

Sample Output 3

4
16
32
48
56
56
55
56
60
64

Explanation for Sample 3

This sample input satisfies the constraints of Subtasks ~1, 2, 6, 7~