[USACO10OPEN]Time Travel S

题目描述

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$。

样例 #1

样例输入 #1

12

a 5

a 3

a 7

s

t 2

a 2

t 4

a 4

s

t 7

s

s

样例输出 #1

5

3

7

3

5

2

7

4

7

2

5

-1

提示

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

| 操作编号 | 操作 | 拥有的奶牛 | 输出 |

| -------- | ----- | ---------- | ---- |

| 1 | a 5 | 5 | 5 |

| 2 | a 3 | 5,3 | 3 |

| 3 | a 7 | 5,3,7 | 7 |

| 4 | s | 5,3 | 3 |

| 5 | t 2 | 5 | 5 |

| 6 | a 2 | 5,2 | 2 |

| 7 | t 4 | 5,3,7 | 7 |

| 8 | a 4 | 5,3,7,4 | 4 |

| 9 | s | 5,3,7 | 7 |

| 10 | t 7 | 5,2 | 2 |

| 11 | s | 5 | 5 |

| 12 | s | / | -1 |