102734: [AtCoder]ABC273 E - Notebook

Problem Statement

We have an integer sequence $A$ and a notebook. The notebook has $10^9$ pages.

You are given $Q$ queries. Each query is of one of the following four kinds:

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.

Initially, $A$ is an empty sequence, and an empty sequence is recorded on each page of the notebook. Process $Q$ queries successively in the given order and print the last term of $A$ after processing each query.

The use of fast input and output methods is recommended because of potentially large input and output.

Constraints

• $1 \leq Q \leq 5 \times 10^5$
• $1 \leq x, y, z \leq 10^9$
• $Q$, $x$, $y$, and $z$ are integers.
• Each of the given queries is of one of the four kinds in the Problem Statement.

Input

The input is given from Standard Input in the following format:

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

Output

For each $i = 1, 2, \ldots, Q$, let $X_i$ be the last element of $A$ after processing up to the $i$-th query, or let $X_i := -1$ if $A$ is empty, and print them in the following format:

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

Sample Input 1

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

Sample Output 1

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

Initially, $A$ is an empty sequence, so $A = ()$, and an empty sequence is recorded on each page of the notebook.

• By the $1$-st query, $3$ is appended to the tail of $A$, resulting in $A = (3)$.
• By the $2$-nd query, the sequence recorded on the $1$-st page of the notebook becomes $(3)$. It remains that $A = (3)$.
• By the $3$-rd query, $4$ is appended to the tail of $A$, resulting in $A = (3, 4)$.
• By the $4$-th query, the sequence recorded on the $2$-nd page of the notebook becomes $(3, 4)$. It remains that $A = (3, 4)$.
• By the $5$-th query, $A$ is replaced by $(3)$, which is recorded on the $1$-st page of the notebook, resulting in $A = (3)$.
• By the $6$-th query, the last term of $A$ is removed, resulting in $A = ()$.
• By the $7$-th query, nothing happens because $A$ is already empty. It remains that $A = ()$.
• By the $8$-th query, $A$ is replaced by $(3,4)$, which is recorded on the $2$-nd page of the notebook, resulting in $A = (3, 4)$.
• By the $9$-th query, the sequence recorded on the $1$-st page of the notebook becomes $(3, 4)$. It remains that $A = (3, 4)$.
• By the $10$-th query, $A$ is replaced by $()$, which is recorded on the $3$-rd page of the notebook, resulting in $A = ()$.
• By the $11$-th query, $A$ is replaced by $(3, 4)$, which is recorded on the $1$-st page of the notebook, resulting in $A = (3, 4)$.

Sample Input 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

Sample Output 2

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

问题描述

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

你会得到$Q$个查询。每个查询属于以下四种之一：

ADD $x$: 将整数$x$添加到$A$的末尾。

DELETE: 如果$A$不为空，则删除$A$的最后一个项；否则什么也不做。

SAVE $y$: 删除笔记本上第$y$页记录的序列，并将当前的$A$记录到第$y$页。

LOAD $z$: 将笔记本上第$z$页记录的序列替换为$A$。

最初，$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$，如果在处理完前$i$个查询后$A$不为空，则令$X_i$为$A$的最后一个元素，否则令$X_i := -1$，然后按照以下格式打印它们：

$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个查询中，$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)$。

样例输入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