题目描述

译自 JOI Open 2023 T2 「セルオートマトン / Cell Automaton」

我们有一个充分大的二维网格，网格由从上到下和从左到右的正方形单元格密铺而成。

有一个单元格是坐标原点。令 $(x,y)$ 表示从原点向右移动 $x$ 个单元格，再向上移动 $y$ 个单元格所到达的单元格。这里，向左移动 $a$ 个单元格意味着向右移动 $-a$ 个单元格；类似地，向下移动 $a$ 个单元格意味着向上移动 $-a$ 个单元格。

在时刻 $0$，单元格 $(X_1,Y_1),(X_2,Y_2),\ldots,(X_N,Y_N)$ 是黑色的，其余单元格是白色的。

对于 $t=0,1,2,\ldots$，根据单元格在 $t$ 时刻的颜色，单元格在 $t+1$ 时刻的颜色按如下方法确定：

1. 如果在时刻 $t$ 时单元格是黑色，那么在时刻 $t+1$ 这个单元格变为灰色。
2. 如果在时刻 $t$ 时单元格是灰色，那么在时刻 $t+1$ 这个单元格变为白色。
3. 如果在时刻 $t$ 时单元格是白色，并且与其相邻的四个单元格（即与其共边的四个单元格）中至少有一个在时刻 $t$ 是黑色的，那么在时刻 $t+1$ 这个单元格变为黑色。否则，它将在时刻 $t+1$ 保持白色。

你有 $Q$ 次查询。对于第 $j$ 个查询，你应该回答在时刻 $T_j$ 时有多少黑色单元格。

给定在时刻 $0$ 时的单元格颜色信息和查询，写一个程序回答询问。

输入格式

第一行两个整数 $N,Q$。

接下来 $N$ 行，每行两个整数 $X_i,Y_i$，表示时刻 $0$ 时黑色单元格的坐标。

接下来 $Q$ 行，每行一个整数 $T_j$，表示查询时刻。

输出格式

输出 $Q$ 行，每行一个整数，表示在时刻 $T_j$ 时黑色单元格的数量。

样例 1

输入

$2$ $3$ $0$ $2$ $1$ $0$ $0$ $1$ $2$

输出

$2$ $8$ $12$

下图展示了在时刻 0 时的单元格情况。因为有 2 个黑色单元格，所以第一个询问的回答是 2。

下图展示了在时刻 1 时的单元格情况。因为有 8 个黑色单元格，所以第二个询问的回答是 8。

下图展示了在时刻 2 时的单元格情况。因为有 12 个黑色单元格，所以第三个询问的回答是 12。 这组样例满足子任务 1,2,6,7 的限制。

样例 2

输入

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

输出

$3$ $12$ $21$ $24$ $26$

该样例满足子任务 $1,2,4,6,7$ 的限制。

样例 3

输入

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

输出

$4$ $16$ $32$ $48$ $56$ $56$ $55$ $56$ $60$ $64$

该样例满足子任务 $1,2,6,7$ 的限制。

数据范围与提示

对于所有数据，满足：

• $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)\ (1\le i < j\le N)$
• $0\le T_j\le 10^9$
• $T_j<T_{j+1}$（查询时刻严格递增）

子任务划分

子任务	附加限制	分值
$1$	$\lvert X_i\rvert ,\lvert Y_i\rvert \le 50$，$T_j\le 50$	$4$
$2$	$\lvert X_i\rvert ,\lvert Y_i\rvert \le 1000$，$T_j\le 1000$	$12$
$3$	$X_i=Y_i$，$Q=1$	$8$
$4$	$X_i=Y_i$	-
$5$	$N\le 2000$，$Q=1$	$17$
$6$	$N\le 2000$	$25$
$7$	无附加限制	$26$