Background

Translated from JOI Open 2023 T2 「セルオートマトン / Cell Automaton」。

Problem Description

We have a sufficiently large 2D grid, tiled with square cells from top to bottom and from left to right.

One cell is the origin. Let $(x,y)$ denote the cell reached by moving $x$ cells to the right from the origin, and then moving $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$, based on the colors of the cells at time $t$, the colors at time $t+1$ are determined as follows:

• If a cell is black at time $t$, then at time $t+1$ this cell becomes gray.
• If a cell is gray at time $t$, then at time $t+1$ this cell becomes white.
• If a cell is white at time $t$, and among its four adjacent cells (i.e., the four cells sharing an edge with it) at least one is black at time $t$, then at time $t+1$ this cell becomes black. Otherwise, it remains white at time $t+1$.

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

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

Input Format

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

The next $N$ lines each contain two integers $X_i,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$.

2 3
0 2
1 0
0
1
2

2
8
12

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

3
12
21
24
26

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

Hint

[Sample Explanation #1]

The figure below shows the state of the cells at time $0$. Since there are $2$ black cells, the answer to the first query is $2$.

The figure below shows the state of the cells at time $1$. Since there are $8$ black cells, the answer to the second query is $8$.

The figure below shows the state of 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$.

[Constraints]

For all testdata, the following hold:

• $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}$

The additional constraints and scores for the subtasks are shown in the table below.

Translated by ChatGPT 5