Каждый день к Грегори Хаусу приходит много больных, и у каждого измеряется уровень гемоглобина в крови. Данные по всем пациентам заносятся в базу данных.
Но волчанка попадается один раз на миллион, а работать с остальными неинтересно. Чтобы Хаус не выгонял больных, Кадди иногда запрашивает статистику по k последним больным: ей хочется знать сумму их уровня гемоглобина.
Также Хаус — мизантроп: он смотрит уровень гемоглобина больного, который поступил к нему позже всех, и, видя, что это точно не волчанка, выписывает его из больницы и удаляет информацию о нем из базы.
Автоматизацию процесса Хаус поручил Чейзу. Но Чейз почему-то не справился с этой задачей и попросил вас ему помочь.
Входные данные: Первой строкой входного файла задано число n ( 1<= n <= 100000 ) — число обращений к базе данных. Запросы к базе выглядят следующим образом: + x ( 1 <=x <= 10 9 ) — добавить пациента с уровнем гемоглобина x в базу, - — удалить последнего пациента из базы, ? k ( 1 <= k <= 100000 ) — вывести суммарный гемоглобин последних k пациентов. Гарантируется, что k не превосходит число элементов в базе. Также гарантируется, что запросов на удаление к пустой базе не поступает. Перед началом работы база данных пуста.
Выходные данные: Для каждого запроса " - " вывести уровень гемоглобина в крови пациента, а для каждого запроса " ? k " — суммарный гемоглобин у последних k поступивших пациентов. Ответы выводите в порядке поступления запросов.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
7
+1
+2
+3
?2
-
-
?1 |
5
3
2
1 |