P9513 [JOI Open 2023] 细胞自动机 / Cell Automaton

**译自 [JOI Open 2023](https://contests.ioi-jp.org/open-2023/index.html) T2 「[セルオートマトン](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/cell/2023-open-cell-statement.pdf) / [Cell Automaton](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/cell/2023-open-cell-statement-en.pdf)」**

我们有一个充分大的二维网格，网格由从上到下和从左到右的正方形单元格密铺而成。 有一个单元格是坐标原点。令 $(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$ 时刻的颜色按如下方法确定： - 如果在时刻 $t$ 时单元格是黑色，那么在时刻 $t+1$ 这个单元格变为灰色。 - 如果在时刻 $t$ 时单元格是灰色，那么在时刻 $t+1$ 这个单元格变为白色。 - 如果在时刻 $t$ 时单元格是白色，并且与其相邻的四个单元格（即，与其共边的四个单元格）中至少有一个在时刻 $t$ 是黑色的，那么在时刻 $t+1$ 这个单元格变为黑色。否则，它将在时刻 $t+1$ 保持白色。 你有 $Q$ 次查询。对于第 $j$ 个查询，你应该回答在时刻 $T_j$ 时有多少黑色单元格。 给定在时刻 $0$ 时的单元格颜色信息和查询，写一个程序回答询问。

第一行两个整数 $N,Q$。 接下来 $N$ 行，每行两个整数 $X_i,Y_i$。 接下来 $Q$ 行，每行一个整数 $T_j$。

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

**【样例解释 #1】** 下图展示了在时刻 $0$ 时的单元格情况。因为有 $2$ 个黑色单元格，所以第一个询问的回答是 $2$。  下图展示了在时刻 $1$ 时的单元格情况。因为有 $8$ 个黑色单元格，所以第二个询问的回答是 $8$。  下图展示了在时刻 $2$ 时的单元格情况。因为有 $12$ 个黑色单元格，所以第三个询问的回答是 $12$。  这组样例满足子任务 $1,2,6,7$ 的限制。 **【样例解释 #2】** 这组样例满足子任务 $1,2,4,6,7$ 的限制。 **【样例解释 #3】** 这组样例满足子任务 $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