Это простая версия задачи. Единственное различие состоит в том, что в этой версии нет запросов удаления.
Изначально у вас есть множество, содержащее единственный элемент — \(0\). Вам нужно обработать \(q\) запросов следующих видов:
- + \(x\) — добавить целое число \(x\) в множество. Гарантируется, что это число не принадлежит множеству до этого запроса;
- ? \(k\) — найти \(k\text{-mex}\) множества.
В нашей задаче мы определяем \(k\text{-mex}\) множества целых чисел как наименьшее неотрицательное целое число \(x\), которое делится на \(k\) и которого нет в множестве.
Выходные данные
Для каждого запроса типа ? выведите единственное целое число — \(k\text{-mex}\) множества.
Примечание
В первом примере:
После первого и второго запроса в множестве будут элементы \(\{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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
15
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 1000000000000000000
? 1000000000000000000
|
3
6
3
3
10
3
2000000000000000000
|
|
2
|
6
+ 100
? 100
+ 200
? 100
+ 50
? 50
|
200
300
150
|