Q

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.

Input

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.

Output

The output should contain the answers for each type 3 query, separated by newlines.

Constraints

• 1 ≤ N ≤ 10⁵
• 0 ≤ any card value ≤ 10⁹.
• 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.

Sample