题目描述

此题与栈练习1相比有两处改动：1. 加强了数据规模；2. 不保证在栈为空时不会进行出栈操作。

给定一个初始为空的栈（元素类型为整数，且绝对值不超过 $10^9$），只有两种操作：入栈和出栈。现给出这些操作，请输出最终栈的栈顶元素。

操作解释：

• 1 x：将元素 $x$ 入栈；
• 2：出栈。若此时栈为空，则输出 impossible!，并忽略本次出栈操作（即栈保持为空）。

在所有操作结束后，若栈为空，则输出 impossible!；否则输出栈顶元素。

输入格式

第一行一个整数 $N$，表示操作个数。
接下来 $N$ 行，每行一个操作。入栈操作为 1 x，出栈操作为 2。

输入不保证在栈空时不会进行出栈操作。

输出格式

对于每次在栈空时进行的出栈操作，输出一行 impossible!。
所有操作结束后，若栈为空，输出一行 impossible!；否则输出栈顶元素。

样例

3
1 2
2
2

impossible!
impossible!

数据范围

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