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

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

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

  • + $$$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$$$ не принадлежит множеству.

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

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

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

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

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

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

После первого и второго запроса в множестве будут элементы $$$\{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$$$.
  • После добавления числа $$$50$$$ множество содержит элементы $$$\{0, 50, 100, 200\}$$$.
  • $$$50\text{-mex}$$$ множества равен $$$150$$$.