/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 366 点
問題文
高橋君はカードゲームが好きで、数字が書かれたカードを机の上に重ねて置いていきます。
カードにはそれぞれ正の整数が書かれています。高橋君はカードを積み重ねて山を作ります。新しいカードを置くときは山の一番上に重ね、カードを取り除くときは一番上（最後に置いたもの）からしか取れません。取り除いたカードは捨てられ、以降の操作には一切関与しません。
はじめ、山にはカードが 1 枚もありません。高橋君は N 回の操作を順番に行います。各操作は以下の 3 種類のいずれかです。
- 追加操作
PUT c：正の整数 c が書かれたカードを山の一番上に置く。 - 除去操作
REMOVE：山の一番上のカードを 1 枚取り除いて捨てる。この操作が行われる時点で、山にカードが 1 枚以上あることが保証される。 - 確認操作
LOOK：現在の山に積まれているすべてのカードに書かれた数字の ビットごとの XOR（排他的論理和）を求める。この操作が行われる時点で、山にカードが 1 枚以上あることが保証される。山にカードが 1 枚だけの場合、XOR の値はそのカードに書かれた数字そのものである。
N 回の操作のうち確認操作だけを出現順に抜き出し、1, 2, 3, \ldots, K と番号を付けます（K は確認操作の総回数です）。i 回目の確認操作で得られた XOR 値を v_i とします。
各 i = 1, 2, \ldots, K について、v_j = v_i かつ j < i を満たす最大の整数 j を求めてください。すなわち、i 回目の確認操作と同じ XOR 値が得られた直近の過去の確認操作の番号を答えてください。そのような j が存在しない場合は -1 を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 各追加操作で与えられる c は 1 \leq c \leq 10^9 を満たす。
REMOVE操作が行われる時点で、山にカードが 1 枚以上ある。LOOK操作が行われる時点で、山にカードが 1 枚以上ある。- N 回の操作のうち、
LOOK操作は 1 回以上含まれる（すなわち K \geq 1）。 - 入力で与えられる数値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
\mathrm{event}_1
\mathrm{event}_2
\vdots
\mathrm{event}_N
- 1 行目には、操作の総回数を表す整数 N が与えられる。
- 続く N 行のうち i 行目には、i 番目の操作 \mathrm{event}_i が以下のいずれかの形式で与えられる。
- 追加操作の場合：
PUT c（文字列PUTの後にスペース区切りで正の整数 c が続く） - 除去操作の場合：
REMOVE - 確認操作の場合：
LOOK
出力
確認操作の総回数を K とする。K 行を出力せよ。
i 行目 (1 \leq i \leq K) には、i 回目の確認操作で得られた XOR 値を v_i として、v_j = v_i かつ j < i を満たす最大の整数 j を出力せよ。そのような j が存在しなければ -1 を出力せよ。
入力例 1
7 PUT 3 PUT 5 LOOK PUT 6 LOOK REMOVE LOOK
出力例 1
-1 -1 1
入力例 2
6 PUT 1 LOOK PUT 2 LOOK PUT 4 LOOK
出力例 2
-1 -1 -1
入力例 3
15 PUT 10 PUT 7 LOOK REMOVE LOOK PUT 3 LOOK PUT 9 LOOK REMOVE REMOVE LOOK PUT 5 LOOK REMOVE
出力例 3
-1 -1 -1 -1 2 -1
入力例 4
24 PUT 1 PUT 2 PUT 4 LOOK REMOVE LOOK REMOVE LOOK PUT 8 LOOK PUT 6 LOOK REMOVE LOOK REMOVE LOOK PUT 3 LOOK PUT 2 LOOK REMOVE LOOK REMOVE LOOK
出力例 4
-1 -1 -1 -1 -1 4 3 -1 -1 8 7
入力例 5
2 PUT 1000000000 LOOK
出力例 5
-1
Score : 366 pts
Problem Statement
Takahashi loves card games and places cards with numbers written on them by stacking them on a desk.
Each card has a positive integer written on it. Takahashi builds a pile by stacking cards. When placing a new card, he puts it on top of the pile, and when removing a card, he can only take the topmost one (the one placed most recently). Removed cards are discarded and are not involved in any subsequent operations.
Initially, the pile contains no cards. Takahashi performs N operations in order. Each operation is one of the following three types:
- Put operation
PUT c: Place a card with the positive integer c written on it on top of the pile. - Remove operation
REMOVE: Remove the topmost card from the pile and discard it. It is guaranteed that the pile contains at least one card when this operation is performed. - Look operation
LOOK: Compute the bitwise XOR (exclusive or) of the numbers written on all cards currently in the pile. It is guaranteed that the pile contains at least one card when this operation is performed. If the pile contains exactly one card, the XOR value is the number written on that card itself.
Extract only the look operations from the N operations in the order they appear, and number them 1, 2, 3, \ldots, K (where K is the total number of look operations). Let v_i be the XOR value obtained by the i-th look operation.
For each i = 1, 2, \ldots, K, find the largest integer j such that v_j = v_i and j < i. In other words, find the number of the most recent past look operation that yielded the same XOR value as the i-th look operation. If no such j exists, output -1.
Constraints
- 1 \leq N \leq 2 \times 10^5
- The value c given in each put operation satisfies 1 \leq c \leq 10^9.
- When a
REMOVEoperation is performed, the pile contains at least one card. - When a
LOOKoperation is performed, the pile contains at least one card. - Among the N operations, at least one
LOOKoperation is included (i.e., K \geq 1). - All numerical values given in the input are integers.
Input
The input is given from standard input in the following format:
N
\mathrm{event}_1
\mathrm{event}_2
\vdots
\mathrm{event}_N
- The first line contains an integer N representing the total number of operations.
- Among the following N lines, the i-th line contains the i-th operation \mathrm{event}_i in one of the following formats:
- For a put operation:
PUT c(the stringPUTfollowed by a positive integer c separated by a space) - For a remove operation:
REMOVE - For a look operation:
LOOK
Output
Let K be the total number of look operations. Output K lines.
On the i-th line (1 \leq i \leq K), let v_i be the XOR value obtained by the i-th look operation, and output the largest integer j such that v_j = v_i and j < i. If no such j exists, output -1.
Sample Input 1
7 PUT 3 PUT 5 LOOK PUT 6 LOOK REMOVE LOOK
Sample Output 1
-1 -1 1
Sample Input 2
6 PUT 1 LOOK PUT 2 LOOK PUT 4 LOOK
Sample Output 2
-1 -1 -1
Sample Input 3
15 PUT 10 PUT 7 LOOK REMOVE LOOK PUT 3 LOOK PUT 9 LOOK REMOVE REMOVE LOOK PUT 5 LOOK REMOVE
Sample Output 3
-1 -1 -1 -1 2 -1
Sample Input 4
24 PUT 1 PUT 2 PUT 4 LOOK REMOVE LOOK REMOVE LOOK PUT 8 LOOK PUT 6 LOOK REMOVE LOOK REMOVE LOOK PUT 3 LOOK PUT 2 LOOK REMOVE LOOK REMOVE LOOK
Sample Output 4
-1 -1 -1 -1 -1 4 3 -1 -1 8 7
Sample Input 5
2 PUT 1000000000 LOOK
Sample Output 5
-1