셀 오토마타

무한히 넓은 2차원 격자가 있다. 격자는 위에서 아래로, 왼쪽에서 오른쪽으로 정사각형 셀로 채워져 있다.

좌표의 원점이 되는 셀이 하나 있다. $(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개 셀 중 하나 이상이 시각 $t$에 검은색이면 시각 $t + 1$에 검은색이 된다. 그렇지 않으면 흰색을 유지한다.

$Q$개의 질의가 주어진다. $j$번째 질의에서는 시각 $T_j$에 검은색인 셀의 개수를 구한다.

첫째 줄에 $N$과 $Q$가 주어진다.

다음 $N$개의 줄에 $X_i$와 $Y_i$가 주어진다.

다음 $Q$개의 줄에 $T_j$가 주어진다.

$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) \ne (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$)
• 주어지는 모든 값은 정수이다.