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