Ksyusha 决定创办一家游戏开发公司。为了在竞争对手中脱颖而出并取得成功,她决定编写自己的游戏引擎。引擎必须支持最初由 $$$n$$$ 不同整数 $$$a_1、a_2、\ldots、a_n$$$ 组成的集合。
该集合将依次进行 $$$m$$$ 操作。这些操作可以是以下类型:
- 将元素 $$$x$$$ 插入集合中;
- 从集合中删除元素$$$x$$$;
- 报告该组的 $$$k$$$ 负载。
集合的 $$$k$$$-load 被定义为最小正整数 $$$d$$$,使得整数 $$$d, d + 1, \ldots, d + (k - 1)$$$ 不会出现在这个集合中。例如,集合 $$$\{3, 4, 6, 11\}$$$ 的 $$$3$$$ 负载是 $$$7$$$,因为集合中不存在整数 $$$7, 8, 9$$$,并且没有更小的值适合。
Ksyusha 正忙于管理任务,因此您必须编写引擎。为所描述的操作提供有效的支持。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
以下几行描述了测试用例。
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 集合的初始大小。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_1 < a_2 < \ldots < a_n \le 2 \cdot 10^6$$$) - 集合的初始状态。
第三行包含一个整数 $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — 操作数。
接下来的 $$$m$$$ 行包含操作。操作按以下格式给出:
- + $$$x$$$ ($$$1 \le x \le 2 \cdot 10^6$$$) — 将元素 $$$x$$$ 插入集合中(保证 $$$x$$$ 不在集合中);
- - $$$x$$$ ($$$1 \le x \le 2 \cdot 10^6$$$) — 从集合中删除元素 $$$x$$$(保证 $$$x$$$ 在集合中);
- ? $$$k$$$ ($$$1 \le k \le 2 \cdot 10^6$$$) — 输出集合的 $$$k$$$ 负载的值。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$,$$$m$$$ 也同样如此。
输出
对于每个测试用例,输出“?”类型操作的答案。
示例
输入 #1
3 5 1 2 5 905 2000000 15 - 2 ? 2 ? 1 - 1 ? 1 + 4 + 2 ? 2 + 6 - 4 + 7 ? 2 ? 3 ? 4 ? 2000000 5 3 4 5 6 8 9 ? 5 - 5 ? 5 + 1 ? 2 - 6 - 8 + 6 ? 5 5 6 7 8 9 10 10 ? 5 - 6 ? 4 - 10 + 5 - 8 + 3 + 2 - 3 + 10
输出 #1
2 2 1 6 3 8 8 2000001 9 9 9 7 1 1