/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 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
入力例 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 番目のクエリによって、 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) となります。
入力例 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
Score : 500 points
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