笔记本

题目描述

我们有一个整数序列 $A$ 和一个笔记本。笔记本有 $10^9$ 页。

给你 $Q$ 个查询。每个查询是以下四种之一:

• ADD x:向 $A$ 的末尾追加整数 $x$。
• DELETE:若 $A$ 非空,则删除 $A$ 的最后一项;否则什么也不做。
• SAVE y:擦除笔记本第 $y$ 页上记录的序列,并把当前的 $A$ 记录到第 $y$ 页。
• LOAD z:用笔记本第 $z$ 页上记录的序列替换 $A$。

初始时,$A$ 是空序列,笔记本每一页都记录着空序列。 按给定顺序依次处理 $Q$ 个查询,并在处理完每个查询后输出 $A$ 的最后一项。

由于输入输出可能很大,建议使用高速输入输出方法。

输入格式

输入按以下格式从标准输入给出:

$Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

输出格式

对于每个 $i = 1, 2, \ldots, Q$,令 $X_i$ 为处理完前 $i$ 个查询后 $A$ 的最后一项,若 $A$ 为空则令 $X_i := -1$,并按以下格式输出:

$X_1$ $X_2$ $\ldots$ $X_Q$

样例

11
ADD 3
SAVE 1
ADD 4
SAVE 2
LOAD 1
DELETE
DELETE
LOAD 2
SAVE 1
LOAD 3
LOAD 1

3 3 4 4 3 -1 -1 4 4 -1 4

初始时,$A$ 是空序列,即 $A = ()$,笔记本每一页都记录着空序列。

通过第 $1$ 个查询,$3$ 被追加到 $A$ 的末尾,得到 $A = (3)$。

通过第 $2$ 个查询,笔记本第 $1$ 页记录的序列变为 $(3)$。$A = (3)$ 保持不变。

通过第 $3$ 个查询,$4$ 被追加到 $A$ 的末尾,得到 $A = (3, 4)$。

通过第 $4$ 个查询,笔记本第 $2$ 页记录的序列变为 $(3, 4)$。$A = (3, 4)$ 保持不变。

通过第 $5$ 个查询,$A$ 被替换为笔记本第 $1$ 页记录的 $(3)$,得到 $A = (3)$。

通过第 $6$ 个查询,$A$ 的最后一项被删除,得到 $A = ()$。

通过第 $7$ 个查询,因为 $A$ 已经为空,所以什么也不发生。$A = ()$ 保持不变。

通过第 $8$ 个查询,$A$ 被替换为笔记本第 $2$ 页记录的 $(3,4)$,得到 $A = (3, 4)$。

通过第 $9$ 个查询,笔记本第 $1$ 页记录的序列变为 $(3, 4)$。$A = (3, 4)$ 保持不变。

通过第 $10$ 个查询,$A$ 被替换为笔记本第 $3$ 页记录的 $()$,得到 $A = ()$。

通过第 $11$ 个查询,$A$ 被替换为笔记本第 $1$ 页记录的 $(3, 4)$,得到 $A = (3, 4)$。

21
ADD 4
ADD 3
DELETE
ADD 10
LOAD 7
SAVE 5
SAVE 5
ADD 4
ADD 4
ADD 5
SAVE 5
ADD 2
DELETE
ADD 1
SAVE 5
ADD 7
ADD 8
DELETE
ADD 4
DELETE
LOAD 5

4 3 4 10 -1 -1 -1 4 4 5 5 2 5 1 1 7 8 7 4 7 1

数据范围

• $1 \le Q \le 5 \times 10^5$
• $1 \le x, y, z \le 10^9$
• $Q$、$x$、$y$、$z$ 均为整数。
• 每个查询都是题目描述中的四种之一。