Hemoglobin

Interview

Time limit2sMemory limit1024 MB

Summary

Process a stream of push, pop, and last-k sum queries on a stack of patient hemoglobin levels, printing each popped value and each requested sum.

Level: Easy3 of 10
Topics: Stack, Prefix sum
Solved: No attempts yet

Problem

Every day, many patients come to Gregory House, and the hemoglobin level of each one is measured. The data for all patients is recorded in a database.

Lupus appears once in a million cases, and working with the rest is not interesting. So that House does not throw patients out, Cuddy sometimes asks for statistics on the last $k$ patients: she wants to know the sum of their hemoglobin levels.

House is also a misanthrope. He looks at the hemoglobin level of the patient who arrived last. If he sees that it is definitely not lupus, he discharges the patient and deletes that patient's information from the database.

Chase was supposed to automate this process. But Chase failed at the task, so he asked you to help him.

Input

The first line contains the number of database requests $n$ ( $1 \le n \le 100000$ ). Each request is one of the following: $+x$ ( $1 \le x \le 10^9$ ) adds a patient with hemoglobin level $x$ to the database, $-$ removes the last patient from the database, and $?k$ ( $1 \le k \le 100000$ ) asks for the sum of hemoglobin levels of the last $k$ patients. It is guaranteed that $k$ does not exceed the number of elements in the database. It is also guaranteed that no removal request is sent to an empty database. The database is empty at the start.

Output

For each $-$ request, print the hemoglobin level of the removed patient. For each $?k$ request, print the sum of hemoglobin levels of the last $k$ patients to arrive. Print the answers in the order the requests were received.

Examples1

Example 1
Input
```
7
+1
+2
+3
?2
-
-
?1
```
Expected output
```
5
3
2
1
```