103086: [Atcoder]ABC308 G - Minimum Xor Pair Query

Problem Statement

There is a blackboard on which you can write integers. Initially, no integer is written on the blackboard. Given $Q$ queries, process them in order.

The query is of one of the following three kinds:

• 1 x : write an $x$ on the blackboard.

• 2 x : erase an $x$ from the blackboard. At the point this query is given, it is guaranteed that at least one $x$ is written on the blackboard.

• 3 : print the minimum possible bitwise XOR of two of the integers written on the blackboard. At the point this query is processed, it is guaranteed that at least two integers are written on the blackboard.

Constraints

• $1\leq Q \leq 3\times 10^5$
• $0\leq x < 2 ^{30}$
• When a query $2$ is given, at least one $x$ is written on the blackboard.
• When a query $3$ is given, at least two integers are written on the blackboard.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

In the $i$-th query, $\mathrm{query}_i$, the kind of query, $c_i$ (one of $1$, $2$, or $3$), is first given. If $c_i = 1$ or $c_i = 2$, an integer $x$ is additionally given.

In other words, each query is in one of the following three formats.

$1$ $x$

$2$ $x$

$3$

Output

Print $q$ lines, where $q$ is the number of queries such that $c_i=3$.

The $j$-th $(1\leq j\leq q)$ line should contain the answer to the $j$-th such query.

Sample Input 1

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

Sample Output 1

8
1
9
0

After processing the $1$-st query, a $2$ is written on the blackboard.

After processing the $2$-nd query, a $2$ and a $10$ are written on the blackboard.

When processing the $3$-rd query, the minimum possible bitwise XOR of two of the integers written on the backboard is $2\oplus 10=8$.

After processing the $4$-th query, a $2$, a $3$, and a $10$ are written on the blackboard.

When processing the $5$-th query, the minimum possible bitwise XOR of two of the integers written on the backboard is $2\oplus 3=1$.

After processing the $6$-th query, a $3$ and a $10$ are written on the blackboard.

When processing the $7$-th query, the minimum possible bitwise XOR of two of the integers written on the backboard is $3\oplus 10=9$.

After processing the $8$-th query, a $3$ and two $10$s are written on the blackboard.

When processing the $9$-th query, the minimum possible bitwise XOR of two of the integers written on the backboard is $10\oplus 10=0$.

问题描述

有一个黑板，你可以在上面写整数。最初，黑板上没有写任何整数。给定$Q$个查询，按顺序处理它们。

查询可能有以下三种类型之一：

• 1 x：在黑板上写下一个$x$。

• 2 x：从黑板上擦除一个$x$。在给出此查询时，保证黑板上至少写了一个$x$。

• 3：打印黑板上两个整数的最小可能按位异或。在处理此查询时，保证黑板上至少写有两个整数。

限制条件

• $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$或$c_i = 2$，还给出一个整数$x$。

换句话说，每个查询可能有以下三种格式之一。

$1$ $x$

$2$ $x$

$3$

输出

打印$q$行，其中$q$是查询数，满足$c_i=3$。

第$j$行（$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$个查询后，黑板上写了一个$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$。