#P18431. Redundant Towers
Redundant Towers
Redundant Towers
Byteland 有 座无线通信塔,编号为 。第 座塔位于 。任意两座塔的横坐标不同,纵坐标也不同。
每座塔的传输半径均为 。也就是说,第 座塔能够一步将消息发送给第 座塔,当且仅当
最初所有塔都处于使用状态。消息只能由使用中的塔传递。
第 座塔称为冗余的,当且仅当同时满足:
- 第 座塔正在使用。
- 对于任意两座其它塔 (,、),如果它们都在使用,并且 原本可以直接或间接向 发送消息,那么不经过第 座塔, 仍然可以直接或间接向 发送消息。
你需要执行 次操作。每次操作指定一座塔,将其使用状态反转:原本使用则停用,原本停用则重新使用。在每次操作后,输出当前冗余塔的数量。
输入格式
第一行包含两个整数 (,)。
接下来 行,第 行包含两个整数 (),表示第 座塔的坐标。保证所有横坐标两两不同,所有纵坐标两两不同。
下一行包含一个整数 (),表示操作次数。
接下来 行,每行包含一个整数 ,表示一次操作的加密值。设 last 是上一次输出的冗余塔数量,在输入开始时 last 初始化为 。本次实际要反转的塔编号为
其中 表示按位异或。保证解密后的编号在 内。上述参数限制只适用于解密后的值,不能要求输入中的加密值在 内;加密值可以为 ,也可以大于 。
本题只有一组输入,不含测试组数。
输出格式
每次操作后输出一行,包含一个整数,表示当前冗余塔的数量。一共输出 行,不输出初始状态的答案。
样例
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
补充说明
样例中实际反转的塔编号依次为 。一个使用中的孤立塔也满足冗余的定义;停用的塔不计入答案。