题目描述

整数列 $A$ とノートがあります。ノートには $10^9$ 枚のページがあります。

$Q$ 個のクエリが与えられます。各クエリは下記の $4$ 種類のいずれかです。

ADD $x$ : 整数 $x$ を $A$ の末尾に追加する。

DELETE : $A$ の末尾の要素を削除する。ただし、$A$ が空である場合は何もしない。

SAVE $y$ : ノートの $y$ ページ目に書かれている数列を消し、代わりに現在の $A$ を $y$ ページ目に書き込む。

LOAD $z$ : $A$ をノートの $z$ ページ目に書かれている数列で置き換える。

はじめ、$A$ は空列であり、ノートのすべてのページには空列の情報が書かれています。 その初期状態から、$Q$ 個のクエリを与えられる順に実行し、各クエリの実行直後における $A$ の末尾の要素を出力してください。

なお、入出力の量が多くなる場合があるので、高速な方法で入出力を行うことを推奨します。

输入格式

入力は以下の形式で標準入力から与えられる。

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

题目大意

有一个版本保存系统，共有 $10^9$ 个版本，每个版本初始都为空列表，还需要维护一个列表（后称为“当前列表”）。
您需要实现如下四种操作：

• ADD x：在当前列表的末尾添加 $x$
• DELETE：如果当前列表非空，把当前列表的末尾最后一个数删除。否则，什么也不做。
• SAVE x：把当前列表保存至第 $x$ 版本（在此后完成的操作不会在第 $x$ 版本中出现，而且保存后当前列表不清空）
• LOAD x：把当前列表变成第 $x$ 版本（直接赋值，而不是添加，而且保存后第 $x$ 版本不清空）
  给定 $q$ 次操作，每次操作是以上四种操作，求每次操作后的当前列表的末尾最后一个数（若数组为空输出 $-1$）。

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

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\ \leq\ Q\ \leq\ 5\ \times\ 10^5$
• $1\ \leq\ x,\ y,\ z\ \leq\ 10^9$
• $Q,\ x,\ y,\ z$ は整数
• 与えられるクエリは問題文中の $4$ 種類のいずれか

Sample Explanation 1

はじめ、$A$ は空列、すなわち $A\ =\ ()$ であり、ノートのすべてのページには空列の情報が書かれています。 - $1$ 番目のクエリによって、 $A$ の末尾に $3$ が追加され、$A\ =\ (3)$ となります。 - $2$ 番目のクエリによって、ノートの $1$ ページ目に書かれた数列が $(3)$ になります。$A$ は変わらず $A\ =\ (3)$ です。 - $3$ 番目のクエリによって、 $A$ の末尾に $4$ が追加され、$A\ =\ (3,\ 4)$ となります。 - $4$ 番目のクエリによって、ノートの $2$ ページ目に書かれた数列が $(3,\ 4)$ になります。$A$ は変わらず $A\ =\ (3,\ 4)$ です。 - $5$ 番目のクエリによって、 $A$ がノートの $1$ ページ目に書かれた数列 $(3)$ で置き換えられ、$A\ =\ (3)$ となります。 - $6$ 番目のクエリによって、 $A$ の末尾の要素が削除され、$A\ =\ ()$ となります。 - $7$ 番目のクエリでは、$A$ がすでに空であるので何もしません。$A$ は変わらず $A\ =\ ()$ です。 - $8$ 番目のクエリによって、 $A$ がノートの $2$ ページ目に書かれた数列 $(3,\ 4)$ で置き換えられ、$A\ =\ (3,\ 4)$ となります。 - $9$ 番目のクエリによって、ノートの $1$ ページ目に書かれた数列が $(3,\ 4)$ になります。$A$ は変わらず $A\ =\ (3,\ 4)$ です。 - $10$ 番目のクエリによって、 $A$ がノートの $3$ ページ目に書かれた数列 $()$ で置き換えられ、$A\ =\ ()$ となります。 - $11$ 番目のクエリによって、 $A$ がノートの $1$ ページ目に書かれた数列 $(3,\ 4)$ で置き換えられ、$A\ =\ (3,\ 4)$ となります。