题目描述

比起栈练习1，本题新增了一个操作：访问栈顶元素（操作编号3），且保证执行访问栈顶元素操作或出栈操作时，栈不为空。 给定一个初始为空的栈，栈内元素为整数且大小不超过109，共有入栈、出栈、访问栈顶三种操作。给出N次操作，按要求输出操作结果。 操作解释： 1 表示入栈，操作后跟随一个入栈元素； 2 表示出栈； 3 表示访问栈顶元素。

输入格式

第一行，一个数字 N，表示操作个数。1≤N≤10^5。 其后 N 行，表示 N 个操作，操作格式如下： 1 后跟一个整数：执行入栈操作； 2：执行出栈操作； 3：执行访问栈顶元素操作。

输出格式

输出共 K 行（K 为操作中访问栈顶元素的次数），每行对应一次访问栈顶元素操作的结果，按操作执行顺序输出。

样例输入

6
1  7
3
2
1  9
1  7
3

样例输出

7
7