Вы думали, что сможете спокойно выехать из Озёрска, погостив у друга? Конечно же, нет. Полицейский опять остановил вас и снова просит решить задачу, чтобы удостовериться, что вы можете выехать из города. Придётся вам решить очередную задачу.
Изначально у вас множество, в котором есть единственный элемент — это 0. Вам нужно будет поддерживать q запросов следующего вида:
• + x — добавить число x в множество. Гарантируется, что раньше его там не было,
• - x — удалить число x из множества. Гарантируется, что это число там есть,
• ? k — найти k − mex множества.
В нашей задаче мы считаем, что k − mex множества — это наименьшее целое неотрицательное число x, которое делится на k и которого нет в множестве.
Входные данные
В первой строке находится целое число q (1 <= q <= 2 · 10
5) — количество запросов.
В следующих q строках находятся описания запросов. Если это запрос добавления, то в формате
+ x (1 <= x <= 10
18), если запрос удаления, то - x (1 <= x <= 10
18), если же запрос поиска, то ? k (1 <= k <= 10
18). Гарантируется, что будет хотя бы один запрос типа ?.
Выходные данные
Для каждого запроса типа ? выведите k − mex множества.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
18
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 100000000
? 100000000
- 4
? 1
? 2 |
3
6
3
3
10
3
200000000
3
4 |
Замечание
После первого и второго запроса во множестве будут элементы 0,1,2. Наименьшее неотрицательное число, которое не делится на 1 и которого нет в множества, равно 3.
После четвертого запроса во множестве будут элементы 0,1,2,4. Наименьшее неотрицательное число, которое не делится на 2 и которого нет в множества, равно 6