Каждый день Летовец измеряет содержание хлорофилла у вновь взошедших растений. Информацию по всем растениям он хранит в базе данных. Очень часто Летовец работает с базой данных, узнает суммарное содержание хлорофилла у 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 |