← 返回题目列表

Codeforces · 706/D

D. 瓦西里的多重套装

中文机器翻译题面 查看原题

作者已经不再讲瓦西里的故事了,所以这里只是一个正式的任务描述。

给你 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$$ 中的最大值。