最小异或对查询

题目描述

有一块可以在上面写整数的黑板。最初,黑板上没有写任何整数。

给定 $Q$ 个查询,请按顺序处理它们。

查询有以下三种:

• 1 x : 在黑板上写下 $x$。
• 2 x : 从黑板上擦除一个 $x$。给出该查询时,保证黑板上至少写有一个 $x$。
• 3 : 输出黑板上写着的整数中,任意两个整数按位异或的最小可能值。处理该查询时,保证黑板上至少写有两个整数。

什么是按位异或?

非负整数 $A$ 和 $B$ 的按位异或 $A \oplus B$ 定义如下。

将 $A \oplus B$ 写成二进制时,第 $2^k$ 位($k \geq 0$)在 $A$ 和 $B$ 的第 $2^k$ 位中恰好有一个为 $1$ 时为 $1$,否则为 $0$。

例如,$3 \oplus 5 = 6$(二进制:$011 \oplus 101 = 110$)。

输入格式

输入按以下格式从标准输入给出:

$Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

在第 $i$ 个查询 $\mathrm{query}_i$ 中,首先给出查询种类 $c_i$(为 $1$、$2$ 或 $3$ 之一)。如果 $c_i = 1$ 或 $c_i = 2$,还会额外给出一个整数 $x$。

也就是说,每个查询是以下三种格式之一。

$1$ $x$

$2$ $x$

$3$

输出格式

设 $q$ 为满足 $c_i=3$ 的查询数量,输出 $q$ 行。

第 $j$ 行($1\leq j\leq q$)输出第 $j$ 个这样的查询的答案。

样例

9
1 2
1 10
3
1 3
3
2 2
3
1 10
3

8
1
9
0

处理第 $1$ 个查询后,黑板上写着 $2$。

处理第 $2$ 个查询后,黑板上写着 $2$ 和 $10$。

处理第 $3$ 个查询时,黑板上任意两个整数按位异或的最小可能值为 $2 \oplus 10 = 8$。

处理第 $4$ 个查询后,黑板上写着 $2$、$3$ 和 $10$。

处理第 $5$ 个查询时,黑板上任意两个整数按位异或的最小可能值为 $2 \oplus 3 = 1$。

处理第 $6$ 个查询后,黑板上写着 $3$ 和 $10$。

处理第 $7$ 个查询时,黑板上任意两个整数按位异或的最小可能值为 $3 \oplus 10 = 9$。

处理第 $8$ 个查询后,黑板上写着 $3$ 和两个 $10$。

处理第 $9$ 个查询时,黑板上任意两个整数按位异或的最小可能值为 $10 \oplus 10 = 0$。

数据范围

• $1 \le Q \le 3\times 10^5$
• $0 \le x \lt 2^{30}$
• 给出查询 2 时,黑板上至少写有一个 $x$
• 给出查询 3 时,黑板上至少写有两个整数
• 输入中的所有值均为整数