Andryusha — young engineer. Now he is designing a modern machine for converting numbers. In the process of construction, more and more blocks are added to the automaton, and Andryusha is interested in how the automaton will work after each such modification.
The automaton is a sequence of blocks of two types: maximizers and minimizers. Each block has some natural number x written on it. The maximizer takes a natural number a as input and outputs the number max ( x , a ) . The minimizer takes a natural number a as input and outputs the number min ( x , a ) .
The automaton works as follows: it takes some natural number, which it feeds to the input of the first block, then what came out of the output of the first block is fed to the input of the second block, and so on. As a result, the machine returns the number obtained at the output of the last block. In other words, the automaton simply passes the number given to it sequentially through all the blocks.
Initially, there is not a single block in the machine, and it simply returns the number it accepts.
Andryusha consistently performs actions with the machine gun. Actions are of three types:
- Add a maximizer with the number x written on it to the end of the sequence of automaton blocks.
- Add a minimizer with the number x written on it to the end of the automaton block sequence.
- Feed the number x to the automaton. In this case, Andryusha wants to know what the machine will return to the exit.
Andryusha has already planned what actions and in what order he will perform. Write a program that will determine the result of Andryusha's automaton, so that he can make sure that it works!
Input
The first line of the input contains a single integer n ( 1 ≤ n ≤ 4·10
5 ) — the total number of Andryusha's actions.
Each of the next n lines contains two integers t and x ( 1 ≤ t ≤ 3 , 1 ≤ x ≤ 10
9 ), where t — this is the next action type. If t = 1 , then Andryusha wants to add a maximizer to the automaton, on which the number x is written. If t = 2 , then Andryusha wants to add a minimizer to the automaton, on which the number x is written. If t = 3 , then Andryusha wants to feed the automaton a number x and find out what the output will be.
Imprint
For each action of the third type, print in a separate line one number, which should be the output of the automaton after this action.
Examples
| # |
Input |
Output |
| 1 |
7
3 5
15
3 2
37
27
38
36 |
5
5
7
7
6 |