分数: 600 点
问题陈述
有一块黑板,你可以在上面写整数。 最初,黑板上没有写任何整数。 给定 Q 查询,按顺序处理。
查询属于以下三种类型之一:
-
1 x:写一个 黑板上的 x 。 -
2 x: 擦除 黑板上的 x 。 在给出这个查询时,保证至少有一个 黑板上写着 x 。 -
3:打印黑板上写的两个整数的最小可能的按位异或。 在处理该查询时,保证至少有两个整数被写在黑板上。
什么是按位异或?
非负整数的按位异或 A 和 B, A \oplus B定义如下。- 当 A \oplus B 以二进制形式写入, 2^k的地方 (k \geq 0)是 1 如果恰好是其中之一 2^k的地点 A 和 B is 1,和 0 否则。
约束
- 1\leq Q \leq 3\times 10^5
- 0\leq x < 2 ^{30}
- 当查询 给定 2 ,至少有一个 给定 x 。
- 当查询 给定 3 ,黑板上至少写出两个整数。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
在 i第一个查询, \mathrm{query}_i,查询类型, c_i (其中之一 1, 2,或 3),首先给出。 如果 c_i = 1 or c_i = 2,一个整数 另外给出了 x 。
换句话说,每个查询都采用以下三种格式之一。
1 x
2 x
3
输出
打印 q 行,其中 q 是查询数量,使得 c_i=3.
的 j-th (1\leq j\leq q) 行应包含以下问题的答案 j-第一个这样的查询。
样本输入 1
9 1 2 1 10 3 1 3 3 2 2 3 1 10 3
示例输出 1
8 1 9 0
处理后 1-st 查询,a 2 。
处理后 2-nd 查询,一个 2 和 黑板上写着 10 。
处理时 3-rd查询,背板上写的两个整数的最小可能按位异或为 2\oplus 10=8.
处理后 4第一个查询,一个 2,一个 3,和 10 。
处理时 5-th 查询,写在背板上的两个整数的最小可能的按位异或为 2\oplus 3=1.
处理后 6第一个查询,一个 3 和 黑板上写着 10 。
处理时 7-th 查询,写在背板上的两个整数的最小可能的按位异或为 3\oplus 10=9.
处理后 8第一个查询,一个 3 和两个 黑板上写着 10。
处理时 9-th 查询,写在背板上的两个整数的最小可能的按位异或为 10\oplus 10=0.