题目描述

此题与栈练习3相比，不保证在执行访问栈顶元素操作或出栈操作时栈不为空。

给定一个初始为空的栈，栈内元素均为整数且绝对值不超过 $10^9$，共有入栈、出栈、访问栈顶三种操作。现给出 $N$ 次操作，请按要求输出对应操作的结果。

操作解释：

• 1 x：将元素 $x$ 入栈；
• 2：出栈；
• 3：访问栈顶元素。

输入格式

第一行一个整数 $N$，表示操作个数。
接下来 $N$ 行，每行一个操作，格式为 1 x、2 或 3。

输出格式

按操作的执行顺序，对每个需要输出的操作输出一行：

• 入栈操作：无输出；
• 出栈操作：若栈为空，输出 impossible!；否则无输出；
• 访问栈顶操作：若栈为空，输出 impossible!；否则输出栈顶元素的值。

样例

6
1 7
3
2
2
1 9
3

7
impossible!
9

数据范围

• $1 \le N \le 10^5$
• $|x| \le 10^9$，$x$ 为整数。