题目描述

FJ购买了一个Acme Time Machine。他现在可以正常地到未来的时间(需要使用机器)，或者跳回到任意一个过去的时间点,在那个点时间会再一次向前走,但是事件有可能会由一个新的，不同的方式展开。在他的时间机器中，FJ永远也不能向前旅行.
FJ想要饲养出最好的奶牛群，所以他在尝试不同的办法，从时间以及事件方面记录下奶牛群多方面的数据。
FJ关心的一个数据是在最短的时间段里他已经得到的奶牛ID号码。请你编写一个程序来帮助他记录牛群的数据,然后在每次命令后，报告最近得到的奶牛的ID(如果他没有奶牛，输出-1)。
FJ有N个要求Q_i,为了方便编号为1..N,表示FJ个人时间的不断更新。
每个要求都是单独的一行。首先是一个单独的字母c('a','s'或't'中的一个)。如果c='a'或c='t',那么在c后面的是一个空格和一个整数K。
* 如果c='a',那么FJ得到了ID为K的奶牛；将这只奶牛放入到牛群队尾；
* 如果c='s',那么FJ卖出最近得到的奶牛(可以保证提出这种类型的要求时FJ至少有一头奶牛)，将这只奶牛除去；
* 如果c='t',那么FJ恰好旅行回到提出第K个要求之前。注意这意味着FJ可能会在平行的时间轴之间旅行(例子中有解释)。牛群恢复到第K个要求提出之前的样子；
举个例子，一共12个要求,下面是奶牛的名字目录和每次要求后得到的结果。
Q# 要求 拥有的奶牛 输出 解释
1 a 5 -> [5] => 5 添加一头ID为5的新奶牛
2 a 3 -> [5,3] => 3 添加一头ID为3的新奶牛
3 a 7 -> [5,3,7] => 7 添加一头ID为7的新奶牛
4 s -> [5,3] => 3 卖出奶牛7
5 t 2 -> [5] => 5 恢复到要求2之前
6 a 2 -> [5,2] => 2 添加一头ID为2的新奶牛
7 t 4 -> [5,3,7] => 7 恢复到要求4之前
8 a 4 -> [5,3,7,4] => 4 添加一头ID为4的新奶牛
9 s -> [5,3,7] => 7 卖出奶牛4
10 t 7 -> [5,2] => 2 恢复到要求7之前
11 s -> [5] => 5 卖出奶牛2
12 s -> [] => -1 卖出奶牛5

输入

第1行:一个单独的整数:N；
第2..N+1行:第i+1行:要求Q_i；

输出

第1..N行:第i行:要求i生效后最近买到的奶牛的ID(如果没有奶牛就输出-1)。

样例输入

12
a 5
a 3
a 7
s
t 2
a 2
t 4
a 4
s
t 7
s
s

样例输出

5
3
7
3
5
2
7
4
7
2
5
-1

提示

【数据规模】
对于40%的数据： 1≤N≤100；
对于60%的数据： 1≤N≤4,000；
对于100%的数据：1≤N≤80,000；1≤K≤1,000,000；