Problem1947--粗心的小明

1947: 粗心的小明

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

粗心的小明总是犯错,所以他每次出错时总是希望撤销。
现在小明手中有一个栈,支持三种基本操作:入栈、出栈和查询栈顶元素,同时还支持两个高级的操作:撤销(撤销只针对入栈和出栈操作)和重做(当撤销过多时可重做,即返回一次撤销)。
注意:
1.每次入栈和出栈都会使当前状态为最新状态,并且之前撤销的操作将无法重做。
2.如果当前状态已经是最原始的状态,则撤销操作无效。
3.如果当前状态已经是最新状态,则重做操作无效。

Input

第一行一个整数n (n≤106)表示操作数
接下来n行,每行代表一个操作:
1 a   表示a(0≤a≤109)入栈
2     表示出栈
3     表示查询栈顶元素
4     表示撤销
5     表示重做

Output

对于每次查询,输出栈顶元素

Sample Input Copy

10
1 1
4
5
1 2
4
3
5
3
2
3

Sample Output Copy

1
2
1