#P18431. Redundant Towers

Redundant Towers

Redundant Towers

Byteland 有 nn 座无线通信塔,编号为 1,2,…,n1,2,\ldots,n。第 ii 座塔位于 (xi,yi)(x_i,y_i)。任意两座塔的横坐标不同,纵坐标也不同。

每座塔的传输半径均为 RR。也就是说,第 ii 座塔能够一步将消息发送给第 jj 座塔,当且仅当

(xi−xj)2+(yi−yj)2≤R.\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}\le R.

最初所有塔都处于使用状态。消息只能由使用中的塔传递。

第 aa 座塔称为冗余的,当且仅当同时满足:

  • 第 aa 座塔正在使用。
  • 对于任意两座其它塔 b,cb,c(1≤b<c≤n1\le b<c\le n,b≠ab\ne a、c≠ac\ne a),如果它们都在使用,并且 bb 原本可以直接或间接向 cc 发送消息,那么不经过第 aa 座塔,bb 仍然可以直接或间接向 cc 发送消息。

你需要执行 qq 次操作。每次操作指定一座塔,将其使用状态反转:原本使用则停用,原本停用则重新使用。在每次操作后,输出当前冗余塔的数量。

输入格式

第一行包含两个整数 n,Rn,R(1≤n≤1051\le n\le10^5,2≤R≤52\le R\le5)。

接下来 nn 行,第 ii 行包含两个整数 xi,yix_i,y_i(1≤xi,yi≤n1\le x_i,y_i\le n),表示第 ii 座塔的坐标。保证所有横坐标两两不同,所有纵坐标两两不同。

下一行包含一个整数 qq(1≤q≤1051\le q\le10^5),表示操作次数。

接下来 qq 行,每行包含一个整数 kk,表示一次操作的加密值。设 last 是上一次输出的冗余塔数量,在输入开始时 last 初始化为 00。本次实际要反转的塔编号为

k⊕last,k\mathbin{\oplus}\texttt{last},

其中 ⊕\oplus 表示按位异或。保证解密后的编号在 1…n1\ldots n 内。上述参数限制只适用于解密后的值,不能要求输入中的加密值在 1…n1\ldots n 内;加密值可以为 00,也可以大于 nn。

本题只有一组输入,不含测试组数。

输出格式

每次操作后输出一行,包含一个整数,表示当前冗余塔的数量。一共输出 qq 行,不输出初始状态的答案。

样例

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

补充说明

样例中实际反转的塔编号依次为 1,2,3,1,2,31,2,3,1,2,3。一个使用中的孤立塔也满足冗余的定义;停用的塔不计入答案。