The game of Q is played using a deck of cards, initially empty. Each card has an integer value associated to it.
There are three types of queries that can be performed:
- 1 X - add a card with value X to the top of the deck.
- 2 - remove the bottom card from the deck.
- 3 - answer the question: what is the largest value of any card in the deck?
You are given a sequence of N queries. Your task is to find the answer to every type 3 query.
The first line of input contains an integer N, denoting the number of queries.
Each of the following N lines of input contains a query, represented using the notation described above.
The output should contain the answers for each type 3 query, separated by newlines.
- 1 ≤ N ≤ 105
- 0 ≤ any card value ≤ 109.
- Multiple cards may have the same value.
- It is guaranteed that there is at least one card in the deck whenever a type 2 or 3 query is performed.