Module: 波尔


Problem

9 /10


多重集和异或

Problem

您有 q 个查询和一个最初仅包含数字 0 的多重集 A。查询分为三种类型:
  • +x ——将数字 x 添加到多重集 A。
  • -x ——从 multiset A 中删除一个数字 x。保证此时 multiset 中至少存在一个数字 x。
  • <李><强>? x —给定一个数字 x,你需要计算数字 x 和多重集 A 中的某个数字 y 的最大按位异或(也称为 XOR)。
多重集——这是一个允许多个相同元素的集合。

输入:
输入的第一行包含数字 q (1 ≤ q ≤ 200000) — Vasiliy 需要处理的请求数。

输入的以下 q 行中的每一行都包含三个字符“+”、“-”中的一个或者 ”?”和数字 xi (1 ≤ xi ≤ 109)。保证输入中至少有一个查询“?”

请注意,数字 0 将始终出现在多重集中。

输出:
对于像“?”这样的每个请求打印一个整数——数字 xi 和多重集 A 中的任何数字的按位异或的最大值。

示例:
  <正文>
输入 输出
10
+8
+9
+11
+ 6
+ 1
? 3
- 8
? 3
? 8
? 11
11
10
14
13