Albert is a school teacher and he is correcting the examination answer sheets of his class. He is getting bored and so decides to play a game. He has three options in this game:
The first line contains the number of test cases T (≤ 50). The description of T test cases follows. Each test case begins with a line with an integer Q (≤ 10000), the number of operations. The next Q lines describe the operations:
1 x: 1 denotes that Albert wants to add an answer sheet to the top of the pile. It's score is x.
2: denotes that Albert wants to throw away the topmost answer sheet in the pile. This operation will only be given if the pile has at least one answer sheet.
3: denotes Albert wants to know the minimum score currently in the pile. This operation will also be given only when there is at least one answer sheet in the pile.
For every operation of type 3, answer one line with an integer, the minimum score currently in the pile.Sample Input
1 7 1 3 1 -1 1 7 3 2 2 3Sample Output
Use 2 stacks, one to represent the actual current pile at every instance (referred as Main), and another stack (Min stack) which is updated only when the current element to be pushed is ≤ all the elements in the Main stack. Whenever a operation of type 3 is encountered, we only have to peek the topmost element of the Min Stack. When a type 2 operation is encountered, we also have to pop an element from Min Stack if topmost(Min Stack) = topmost(Main Stack)