题目描述

栈是一种数据结构。现在你要支持几种操作：

• push $x$，将 $x$ 这个元素放到栈顶。
• pop，将栈顶元素删除。
• top，询问栈顶元素是多少。

建议手动实现一遍，再用内置栈或双端队列完成。

输入格式

第一行一个整数 $m$，表示操作个数。

接下来 $m$ 行，每行一个上面所述的操作。

输出格式

输出若干行，对于每个查询操作，输出答案。

样例输入

10
push 1
push 2
top
pop
top
push 3
top
pop
push 4
top

样例输出

2
1
3
4

数据规模

对于 $100\%$ 的数据，保证 $1≤m≤10^5$。

对于 push 操作，保证 $1≤x≤10^9$。

对于 pop 和 top 操作，保证栈非空。