H. Ксюша и загруженное множество
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ксюша решила основать компанию по производству игр. Чтобы выделиться среди конкурентов и добиться успеха, она решила написать свой игровой движок. Движок должен поддерживать множество, изначально состоящее из $$$n$$$ различных целых чисел $$$a_1, a_2, \ldots, a_n$$$.

К множеству будут последовательно применяться $$$m$$$ операций. Операции бывают следующих типов:

  • Вставить элемент $$$x$$$ в множество;
  • Удалить элемент $$$x$$$ из множества;
  • Сообщить $$$k$$$-загруженность множества.

$$$k$$$-загруженностью множества называется такое минимальное целое положительное число $$$d$$$, что числа $$$d, d + 1, \ldots, d + (k - 1)$$$ не встречаются в этом множестве. Например, $$$3$$$-загруженность множества $$$\{3, 4, 6, 11\}$$$ равна $$$7$$$, так как числа $$$7, 8, 9$$$ отсутствуют в множестве, а никакое меньшее значение не подходит.

Ксюша занята менеджерскими делами, поэтому движок придётся писать вам. Реализуйте эффективную поддержку описанных операций.

Входные данные

В первой строке дано целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите ответы на операции типа «?».

Пример
Входные данные
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
Выходные данные
2 2 1 6 3 8 8 2000001 
9 9 9 7 
1 1