题目描述

Farmer John 买了台时光机，这使得他可以方便地管理自己的奶牛群。

他现在有 $N$ 个操作（$1 \leq N \leq 8 \times 10^4$），每次操作仅可能是如下三种之一：

1. a x：添加一头编号为 $x$ 的奶牛（$1 \leq x \leq 10^6$）。
2. s：卖掉最近添加的奶牛（保证此时至少有一头奶牛）。
3. t x：回到第 $x$ 次操作前的状态（保证第 $x$ 次操作存在）。

你需要在 FJ 执行每次操作后输出他拥有的最新的奶牛的编号。特别地，如果没有奶牛，输出 $-1$。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，每行描述一次操作。

输出格式

第 $i$ 行输出第 $i$ 次操作后 FJ 拥有的最新的奶牛的编号。特别地，如果没有奶牛，输出 $-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

提示

下面是样例解释，其中拥有的奶牛已经按添加顺序排好。