You have an empty sequence, and you will be given N queries. Each query is one of these three types:
-
1 x - Push the element x into the stack.
-
2 - Delete the element present at the top of the stack.
-
3 - Print the maximum element in the stack.
Input Format: The first line of input contains an integer, N. The next N lines each contain an above mentioned query. (It is guaranteed that each query is valid.)
Output Format: For each type 3 query, print the maximum element in the stack on a new line.
Constraints:
1 ≤ N ≤ 105
1 ≤ x ≤ 109
1 ≤ type ≤ 3
Here is an examples:
Input
|
Output
|
9
1 97
2
1 20
2
1 26
1 20
3
1 91
3
|
26
91
|