AT_abc273_e [ABC273E] Notebook

[problemUrl]: https://atcoder.jp/contests/abc273/tasks/abc273_e 整数列 $ 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 $

### 制約 - $ 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) $ となります。