作者已经不再讲瓦西里的故事了,所以这里只是一个正式的任务描述。
给你 q 个查询和一个多重集 A,最初只包含整数 0。查询分为三种类型:
1.“+ x”— 将整数 x 添加到多重集 A。
2. "- x" — 从多重集 A 中删除一次出现的整数 x。保证在本次查询之前多重集 A 中至少存在一个 x。
3. "? x" - 给定整数 x,需要计算值 $$\max_{y \in A} (x \oplus y)$$,即整数 x 和多重集 A 中的某个整数 y 的按位异或(也称为 XOR)的最大值。
Multiset 是一个集合,其中允许相等的元素。
输入
输入的第一行包含一个整数 q (1 ≤ q ≤ 200 000) - Vasiliy 必须执行的查询数。
输入的以下 q 行中的每一行都包含三个字符“+”、“-”或“?”之一和整数 xi (1 ≤ xi ≤ 109)。保证至少有一个第三种类型的查询。
请注意,整数 0 将始终出现在集合 A 中。
输出
对于每个“?”类型的查询打印一个整数 - 整数 xi 和多重集 A 中的某个整数的按位异或 (XOR) 的最大值。
示例
输入 #1
10 + 8 + 9 + 11 + 6 + 1 ? 3 - 8 ? 3 ? 8 ? 11
输出 #1
11 10 14 13
注意
经过前五次操作后,多重集 A 包含整数 0、8、9、11、6 和 1。
第六个查询的答案是整数 $$1 1 = 3 \oplus 8$$ — 整数 $$3 \oplus 0 = 3$$、$$3 \oplus 9 = 10$$、$$3 \oplus 11 = 8$$、$$3 \oplus 6 = 5$$ 和 $$3 \oplus 1 = 2$$ 中的最大值。