Рабочее место участника

Каждый день к Грегори Хаусу приходит много больных, и у каждого измеряется уровень гемоглобина в крови. Данные по всем пациентам заносятся в базу данных.

Но волчанка попадается один раз на миллион, а работать с остальными неинтересно. Чтобы Хаус не выгонял больных, Кадди иногда запрашивает статистику по `k` последним больным: ей хочется знать сумму их уровня гемоглобина.

Также Хаус – мизантроп: он смотрит уровень гемоглобина больного, который поступил к нему позже всех, и, видя, что это точно не волчанка, выписывает его из больницы и удаляет информацию о нем из базы.

Автоматизацию процесса Хаус поручил Чейзу. Но Чейз почему-то не справился с этой задачей и попросил вас ему помочь.

Первой строкой входного файла задано число `n` (`1\ ≤\ n\ ≤\ 100000`) – число обращений к базе данных. Запросы к базе выглядят следующим образом: `+x` (`1\ ≤\ x\ ≤\ 10^9`) – добавить пациента с уровнем гемоглобина `x` в базу, `-` – удалить последнего пациента из базы, `?k` (`1\ ≤\ k\ ≤\ 100000`) – вывести суммарный гемоглобин последних `k` пациентов. Гарантируется, что `k` не превосходит число элементов в базе. Также гарантируется, что запросов на удаление к пустой базе не поступает. Перед началом работы база данных пуста.

Для каждого запроса `-` вывести уровень гемоглобина в крови пациента, а для каждого запроса `?k` – суммарный гемоглобин у последних `k` поступивших пациентов. Ответы выводите в порядке поступления запросов.

7
+1
+2
+3
?2
-
-
?1

5
3
2
1