配点 : $500$ 点

問題文

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

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

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

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

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

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

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

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

制約

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

入力

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

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

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$ 番目のクエリによって、 $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)$ となります。

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