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\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.

$NQ$

$X_1{Y}_1$

$X_2{Y}_2$

$⋮$

$X_N{Y}_N$

$T_1$

$T_2$

$⋮$

$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 100000$.
• $1\le Q\le 500000$.
• $|X_i|\le {10}^9$ ($1\le i\le N$).
• $|Y_i|\le {10}^9$ ($1\le i\le N$).
• $(X_i,Y_i)\ne (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 1000$ ($1\le i\le N$), $|Y_i|\le 1000$ ($1\le i\le N$), $T_j\le 1000$ ($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 2000$, $Q=1$.
6. (25 points) $N\le 2000$.
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$