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:

- add a card with value`1 X`to the top of the deck.`X`- remove the bottom card from the deck.`2`- answer the question: what is the largest value of any card in the deck?`3`

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

**lines of input contains a query, represented using the notation described above.**

`N`### Output

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

### Constraints

`1 ≤ N ≤ 10`^{5}`0 ≤ any card value ≤ 10`^{9}.- 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

Input | Output |
---|---|

71 6 3 1 9 1 4 2 2 3 | 64 |