Every day, many patients come to Gregory House, and everyone has their hemoglobin levels measured. Data for all patients are entered into the database.
But lupus comes across once in a million, and working with the rest is not interesting. To prevent House from expelling patients, Cuddy sometimes asks for statistics on k last patients: she wants to know the sum of their hemoglobin levels.
Also House — misanthrope: he looks at the hemoglobin level of the patient, who came to him later than everyone else, and, seeing that it is definitely not lupus, discharges him from the hospital and deletes information about him from the database.
Case was tasked by House to automate the process. But for some reason Chase could not cope with this task and asked you to help him.
Input: The first line of the input file is a number n ( 1<= n ;<= 100000 ) — number of database hits. Database queries look like this: + x ( 1 <=x < = 10 9 ) — add a patient with a hemoglobin level x to the database, - — remove the last patient from the database, ? k ( 1 <= k <= 100000 ) — display the total hemoglobin of the last k patients. It is guaranteed that k does not exceed the number of elements in the base. It is also guaranteed that there are no requests for deletion to an empty database. The database is empty before starting.
Output: For each request " - " display the level of hemoglobin in the patient's blood, and for each query " ? k " — total hemoglobin in the last k admitted patients. Output the answers in the order in which requests are received.
Examples
| # |
Input |
Output |
| 1 |
7
+1
+2
+3
?2
-
-
?1 |
5
3
2
1 |