Problem Description

We have a sufficiently large two-dimensional grid, which is tiled with square cells from top to bottom and from left to right.

One cell is the coordinate origin. Let $(x, y)$ denote the cell reached by moving $x$ cells to the right from the origin and then $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$, the color of a cell at time $t+1$ is determined based on its color at time $t$ as follows:
- If the cell is black at time $t$, it becomes gray at time $t+1$.
- If the cell is gray at time $t$, it becomes white at time $t+1$.
- If the cell is white at time $t$ and at least one of its four adjacent cells (i.e., the four cells sharing an edge with it) is black at time $t$, it becomes black at time $t+1$. Otherwise, it remains white at time $t+1$.

You have $Q$ queries. For the $j$-th query, you should answer how many cells are black at time $T_j$.

Given the cell color information at time $0$ and the queries, write a program to answer the queries.

Input Format

The first line contains two integers $N$ and $Q$.

The next $N$ lines each contain two integers $X_i$ and $Y_i$.

The next $Q$ lines each contain one integer $T_j$.

Output Format

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

Sample Input and Output

Input Sample #1

2 3
0 2
1 0
0
1
2

Output Sample #1

2
8
12

Input Sample #2

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

Output Sample #2

3
12
21
24
26

Input Sample #3

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

Output Sample #3

4
16
32
48
56
56
55
56
60
64

Notes/Hints

[Sample Explanation #1]

The following image shows the cells at time $0$. Since there are $2$ black cells, the answer to the first query is $2$.

The following image shows the cells at time $1$. Since there are $8$ black cells, the answer to the second query is $8$.

The following image shows 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$.

[Data Range]

For all data, the following constraints are satisfied:

• $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)$ for $1 \le i < j \le N$
• $0 \le T_j \le 10^9$
• $T_j < T_{j+1}$

Detailed subtask additional constraints and scores are as follows:

见题面 Input 部分

见题面 Output 部分