Minimum in the stack

Implement a data structure with the next operations:

1. Push $x$ to the end of the structure.

2. Pop the last element from the structure.

3. Print the minimum element in the structure.

Input

The first line contains the number of operations $n(1\le n\le 10^6)$. Each of the next $n$ lines contains one operation. The $i$-th line contains the number $t_i$ — the type of operation:

• 1 in the case of a push operation;

• 2 in the case of a pop operation;

• 3 if the operation asks to find minimum;

In the case of a push operation, next comes the integer $x(-10^9\le x\le 10^9)$ — element to be inserted into the structure. It is guaranteed that before each pop or getMin operation the structure is not empty.

Output

For each getMin operation, print on a separate line one number — the minimal element in the structure.

Examples