分数: 500 点
问题陈述
我们有一个整数序列 A 和一个笔记本。 笔记本有 10^9 页。
你被给予 Q 查询。 每个查询属于以下四种类型之一:
ADD x: append an integer x to the tail of A.
DELETE: remove the last term of A if A is not empty; do nothing otherwise.
SAVE y: erase the sequence recorded on the y-th page of the notebook, and record the current A onto the y-th page.
LOAD z: replace A with the sequence recorded on the z-th page of the notebook.
最初, 黑板上写着 A 是一个空序列,笔记本的每一页上都记录了一个空序列。 工艺流程 Q 按给定顺序依次查询并打印最后一项 A 处理每个查询后。
由于潜在的大量输入和输出,建议使用快速输入和输出方法。
约束
- 1 \leq Q \leq 5 \times 10^5
- 1 \leq x, y, z \leq 10^9
- Q, x, y,和 z 是整数。
- 每个给定的查询都是问题陈述中四种类型之一。
输入
输入由标准输入按以下格式给出:
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
输出
对于每个 i = 1, 2, \ldots, Q,让 X_i 是最后一个元素 A 处理后 i-第一个查询,或者让 X_i := -1 if A 为空,按以下格式打印:
X_1 X_2 \ldots X_Q
示例输入 1
11 ADD 3 SAVE 1 ADD 4 SAVE 2 LOAD 1 DELETE DELETE LOAD 2 SAVE 1 LOAD 3 LOAD 1
示例输出 1
3 3 4 4 3 -1 -1 4 4 -1 4
最初, 黑板上写着 A 是一个空序列,所以 A = (),笔记本的每一页上都会记录一个空序列。
- 由 1-st 查询, 3 附加到尾部 A,导致 A = (3).
- 由 2-nd查询,记录在 1笔记本的第页变为 (3)。 仍然是 A = (3).
- 由 3-rd 查询, 4 附加到尾部 A,导致 A = (3, 4).
- 由 4第一个查询,记录在 2笔记本的第页变成 (3, 4)。 仍然是 A = (3, 4).
- 由 5第一个查询, A 被替换为 (3),记录在 1- 笔记本的第页,导致 A = (3).
- 由 6第一个查询,最后一项 A 被删除,导致 A = ().
- 由 7-th 查询,没有任何反应,因为 A 已为空。 仍然是 A = ().
- 由 8第一个查询, A 被替换为 (3,4),记录在 2- 笔记本的第 3 页,导致 A = (3, 4).
- 由 9第一个查询,记录在 1笔记本的第页变为 (3, 4)。 仍然是 A = (3, 4).
- 由 10第一个查询, A 被替换为 (),记录在 3- 笔记本的第一页,导致 A = ().
- 由 11第一个查询, A 被替换为 (3, 4),记录在 1- 笔记本的第页,导致 A = (3, 4).
示例输入 2
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
示例输出 2
4 3 4 10 -1 -1 -1 4 4 5 5 2 5 1 1 7 8 7 4 7 1