D2. Баланс (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное различие состоит в том, что в этой версии есть запросы удаления.

Изначально у вас есть множество, содержащее единственный элемент — $$$0$$$. Вам нужно обработать $$$q$$$ запросов следующих видов:

  • + $$$x$$$ — добавить целое число $$$x$$$ в множество. Гарантируется, что это число не принадлежит множеству до этого запроса;
  • - $$$x$$$ — удалить целое число $$$x$$$ из множества. Гарантируется, что это число принадлежит множеству;
  • ? $$$k$$$ — найти $$$k\text{-mex}$$$ множества.

В нашей задаче мы считаем, что $$$k\text{-mex}$$$ множества — это наименьшее неотрицательное целое число $$$x$$$, которое делится на $$$k$$$ и которого нет в множестве.

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

В первой строке находятся целое число $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — количество запросов.

В следующих $$$q$$$ строках находится описание запросов.

Запрос добавления числа $$$x$$$ описывается как + $$$x$$$ ($$$1 \leq x \leq 10^{18}$$$). Гарантируется, что число $$$x$$$ не принадлежит множеству.

Запрос удаления числа $$$x$$$ описывается как - $$$x$$$ ($$$1 \leq x \leq 10^{18}$$$). Гарантируется, что число $$$x$$$ принадлежит множеству.

Запрос нахождения $$$k\text{-mex}$$$ описывается как ? $$$k$$$ ($$$1 \leq k \leq 10^{18}$$$).

Гарантируется, что хотя бы один запрос имеет тип ?.

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

Для каждого запроса типа ? выведите единственное целое число — $$$k\text{-mex}$$$ множества.

Примеры
Входные данные
18
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 1000000000000000000
? 1000000000000000000
- 4
? 1
? 2
Выходные данные
3
6
3
3
10
3
2000000000000000000
3
4
Входные данные
10
+ 100
? 100
+ 200
? 100
- 100
? 100
+ 50
? 50
- 50
? 50
Выходные данные
200
300
100
100
50
Примечание

В первом примере:

После первого и второго запроса во множестве будут элементы $$$\{0, 1, 2\}$$$. Наименьшее неотрицательное число, которое делится на $$$1$$$ и которого нет в множества, равно $$$3$$$.

После четвертого запроса во множестве будут элементы $$$\{0, 1, 2, 4\}$$$. Наименьшее неотрицательное число, которое делится на $$$2$$$ и которого нет в множества, равно $$$6$$$.

Во втором примере:

  • Изначально множество содержит только элемент $$$\{0\}$$$.
  • После добавления числа $$$100$$$ множество содержит элементы $$$\{0, 100\}$$$.
  • $$$100\text{-mex}$$$ множества равен $$$200$$$.
  • После добавления числа $$$200$$$ множество содержит элементы $$$\{0, 100, 200\}$$$.
  • $$$100\text{-mex}$$$ множества равен $$$300$$$.
  • После удаления числа $$$100$$$ множество содержит элементы $$$\{0, 200\}$$$.
  • $$$100\text{-mex}$$$ множества равен $$$100$$$.
  • После добавления числа $$$50$$$ множество содержит элементы $$$\{0, 50, 200\}$$$.
  • $$$50\text{-mex}$$$ множества равен $$$100$$$.
  • После удаления числа $$$50$$$ множество содержит элементы $$$\{0, 200\}$$$.
  • $$$100\text{-mex}$$$ множества равен $$$50$$$.