#5007. TCP协议

内存限制:128 MiB 时间限制:10 Sec

题目描述

在如今的网络中,TCP是一种被广泛使用的网络协议,它在传输层提供了可靠的通信服务。众所周知,网络是存在
时延的,例如用户先后向服务器发送了两个指令op1和op2,并且希望服务器先处理指令op1,再处理指令op2;但由
于网络时延,这两个指令可能会失序到达,而导致服务器先执行了指令op2,这是我们不希望看到的。TCP协议拥有
将失序到达的报文按顺序重组的功能,一种方法是给每一个报文打上一个时间戳。而你今天要实现的功能比这个要
简单很多。我们需要你维护一个服务器,这个服务器的功能是一个简单的栈,你会接收三种用户的指令:
push x t --- 表示将x元素入栈,这条指令的时间戳为t
pop t --- 表示将栈顶元素弹出,这条指令的时间戳为t
peak t --- 用户询问现在栈顶元素的值,这条指令的时间戳为t
当一条时间戳为t的指令到达时,你需要进行如下处理:
1.将所有之前执行的时间戳大于t的push和pop指令全部撤销
2.执行当前这条指令
3.按时间戳顺序重新执行在第1步被撤销的指令
注意你不需要撤销以及重新执行之前已经执行过的peak指令
也就是说每一条peak指令只有在它到达的时候会被执行一次。
我们保证每一条指令的时间戳都是唯一的;
若你在需要执行一条pop指令时发现当前栈为空,则当前你可以忽略这条指令。

输入格式

第一行包含一个整数n,表示指令总数。
接下来n行按指令到达服务器的顺序给出每一条指令,有三种类型
push x t
pop t
peak t
1 <= n <= 300000,0 <= x,t <= 1000000000

输出格式

对于每一条peak指令,输出对应的答案占一行;若栈为空,输出-1。

样例

样例输入


			
7
push 100 3
push 200 7
peak 4
push 50 2
pop 5
peak 6
peak 8

样例输出


			
100
50
200

数据范围与提示