我们有一个足够大的二维网格。网格由从上到下、从左到右排列的方形单元格组成。

有一个单元格作为坐标原点。令 $(x, y)$ 表示从原点向右移动 $x$ 个单元格距离、向上移动 $y$ 个单元格距离后到达的单元格。此处，向左移动 $a$ 个单元格距离意味着向右移动 $-a$ 个单元格距离。类似地，向下移动 $a$ 个单元格距离意味着向上移动 $-a$ 个单元格距离。

在时间 $0$，单元格 $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ 为黑色，其余所有单元格均为白色。

对于 $t = 0, 1, 2, \dots$，时间 $t+1$ 时单元格的颜色由时间 $t$ 时单元格的颜色按以下方式决定：

• 如果一个单元格在时间 $t$ 是黑色，则该单元格在时间 $t+1$ 变为灰色。
• 如果一个单元格在时间 $t$ 是灰色，则该单元格在时间 $t+1$ 变为白色。
• 如果一个单元格在时间 $t$ 是白色，且其 4 个相邻单元格（即共享边的 4 个单元格）中至少有一个在时间 $t$ 是黑色，则该单元格在时间 $t+1$ 变为黑色。否则，它在时间 $t+1$ 保持白色。

你有 $Q$ 次询问。对于第 $j$ 次（$1 \le j \le Q$）询问，你需要回答时间 $T_j$ 时黑色单元格的数量。

编写一个程序，根据时间 $0$ 时单元格颜色的信息和询问，回答这些询问。

输入格式

从标准输入读取以下数据：

$N \ Q$ $X_1 \ Y_1$ $X_2 \ Y_2$ $\vdots$ $X_N \ Y_N$ $T_1$ $T_2$ $\vdots$ $T_Q$

输出格式

输出 $Q$ 行到标准输出。第 $j$ 行应包含时间 $T_j$ 时黑色单元格的数量。

数据范围

• $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$)
• 给定值均为整数。

子任务

1. (4 分) $|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 分) $|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 分) $X_i = Y_i$ ($1 \le i \le N$), $Q = 1$
4. (8 分) $X_i = Y_i$ ($1 \le i \le N$)
5. (17 分) $N \le 2\,000$, $Q = 1$
6. (25 分) $N \le 2\,000$
7. (26 分) 无附加限制

样例

样例输入 1

2 3
0 2
1 0
0
1
2

样例输出 1

2
8
12

样例输入 2

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

样例输出 2

3
12
21
24
26

样例输入 3

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

样例输出 3

4
16
32
48
56
56
55
56
60
64

Figure 1. Grid state at time t=0