Stack max

Bạn có một Ngăn xếp (Stack) rỗng và hiện có \(N\) truy vấn. \(N\) truy vấn này có 3 loại:

• Loại \(1\) ở dạng 1 x, đẩy phần tử có giá trị \(x\) vào Stack.
• Loại phần tử trên cùng của Stack.
• Loại \(3\), in ra giá trị của phần tử lớn nhất có trong Stack.

Hãy lập trình đọc vào các truy vấn và thực hiện như đã mô tả.

Input

• Dòng đầu tiên chứa một nguyên dương \(N\), là số câu truy vấn tiếp theo \((1 \leq N \leq 10^5)\)
• \(N\) dòng tiếp theo, mỗi dòng sẽ chứa:
• Nếu là truy vấn \(1\), dòng sẽ chứa 1 x với \(x\) là giá trị phần tử cần thêm vào. \((1 \leq x \leq 10^9)\)
• Nếu là truy vấn \(2\) hoặc \(3\), dòng sẽ chứa một số nguyên là \(2\) hoặc \(3\) tương ứng.

Dữ liệu Input đảm bảo không có truy vấn \(2\), \(3\) khi Stack rỗng.

Output

Lần lượt theo thứ tự của truy vấn, với mỗi truy vấn \(3\) in ra đáp án trên một dòng.

Example

10
1 97
2
1 20
2
1 26
1 20
2
3
1 91
3

26
91