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

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

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

2020华为杯程序设计竞赛