Расширение Всадников
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Четыре Всадника продолжают свои тщательно спланированные представления по всему миру. Они то исчезают, то снова появляются на сцене, оставляя за собой множество загадок.

Рассмотрим динамическое множество команд иллюзионистов. Каждая команда с номером $$$i$$$ характеризуется двумя параметрами $$$x_i$$$ и $$$k_i$$$ (обратите внимание, что оба параметра у двух разных команд могут совпадать).

Начиная с дня $$$t = 1$$$, команда живёт по бесконечному циклу:

- в течение первых $$$k_i$$$ дней команда активно выступает с интенсивностью $$$x_i$$$;
- затем следующие $$$k_i$$$ дней команда полностью исчезает, готовя новые фокусы и не внося никакого вклада в общую «интенсивность магии».

Затем цикл повторяется: $$$k_i$$$ дней выступлений, $$$k_i$$$ дней тишины, и так далее.

Необходимо обрабатывать запросы от разных наблюдателей (Интерпол, полиция, фанаты и таинственные заказчики), которые хотят знать, какая суммарная «интенсивность магии» наблюдается в тот или иной день.

Поддерживаются три типа запросов:

1. + $$$x$$$ $$$k$$$ — на сцену выходит новая команда иллюзионистов с параметрами $$$x$$$ и $$$k$$$;
2. - $$$x$$$ $$$k$$$ — команда с параметрами $$$x$$$ и $$$k$$$ прекращает участвовать в игре;
3. ? $$$t$$$ — требуется узнать суммарную интенсивность всех команд в день с номером $$$t$$$.

Помогите наблюдателям узнавать ответы на все запросы третьего типа.

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

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

Каждая из следующих $$$q$$$ строк содержит один запрос одного из трёх описанных выше типов.

В запросах 1 и 2 типа заданы целые числа $$$x$$$ и $$$k$$$, они описывают добавление и удаление команды с параметрами $$$x$$$ и $$$k$$$ соответственно ($$$1 \le x \le 10^3$$$; $$$1 \le k \le 2 \cdot 10^5$$$).

В запросе третьего типа задано целое число $$$t$$$ — номер дня ($$$1 \le t \le 2 \cdot 10^5$$$).

Гарантируется, что для каждого запроса второго типа соответствующая команда ранее была добавлена запросом первого типа и к этому моменту ещё не была удалена.

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

Для каждого запроса третьего типа выведите в отдельной строке одно целое число — суммарную интенсивность магии в интересующий день.

Примеры

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

    5+ 1 1? 1? 2? 3? 4

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

    1
    0
    1
    0

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

    12+ 3 2+ 5 3? 1? 2? 3+ 4 2? 4- 5 3? 5? 6+ 2 4? 7

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

    8
    8
    5
    0
    7
    7
    0