Hamako Online Judge

TLE
2sec

MLE
256MB

得点
74

問題

Kamba君は自己紹介ページを作成しています。Kamba君は優秀なので、自作アプリケーション「KambaWord」を使用しています。このアプリケーションは、キー入力をあらかじめ登録したコマンドに紐づけることができます。
ただし、このアプリケーションは、入力を即時には処理せず、入力されたキーを一時保存してから順番に処理します。このとき、以下のクエリに答えてください。

あらかじめ、$M$ 個のキーと、それに対応する処理内容 $S$ が与えられる。
クエリとして、以下の2種類が $Q$ 個与えられる。

IN：キー $c$ を入力し、バッファーの末尾に追加する。
OUT:バッファーの先頭にあるキー $c$ を処理し、対応するコマンドを出力する。
ただし登録されていないキーならば $-1$ を出力し、バッファーが空ならば $0$ を出力すること。

入力

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

$M$
$C_1$ $S_1$
$C_2$ $S_2$
$:$
$:$
$C_M$ $S_M$
$Q$
$query_1$
$query_2$
$:$
$:$
$query_Q$

あらかじめ登録されているコマンドの総数 $M$ が与えられる。その後、$M$ 行に渡って、キー $C_i$ （文字）とコマンド $S_i$ （文字列）が与えられる。そして、クエリの総数 $Q$ が与えられる。その後、$Q$ 行に渡って各クエリが渡される。

クエリ IN は以下のように渡される。

$IN$ $C$

$C$ は入力されたキーを表す。

また、クエリ OUT は以下のように渡される。

$OUT$

出力

出力は1行ずつ区切って行うこと。
また、出力がない場合を除いて、最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

$1 \leq M \leq 52$
$1 \leq |S| \leq 74$ ( ただし $|S|$ は文字列 $S$ の長さを表す。）
文字列 $S$ はアルファベットで構成される。
文字 $C$ はアルファベットで構成される。
あらかじめ登録されているコマンドのキーは重複していない。
$1 \leq Q \leq 7.4 \times 10^{5}$

入出力例

入力例1

3
a insert
b delete
c print
7
IN a
IN c
OUT
IN b
OUT
OUT
OUT

出力例1

insert
print
delete
0

登録されているコマンドは以下の通りです。

キー $a$ : $insert$
キー $b$ : $delete$
キー $c$ : $print$

次に各クエリを見ていきます。

クエリ$IN$で $a$ というキーが入力されたので、バッファーに格納します。

クエリ$IN$で $b$ というキーが入力されたので、バッファーに格納します。

クエリ$OUT$でバッファーの先頭から一つ取り出してコマンドを出力します。現時点のバッファーは ${ a, b }$ となっているので先頭の要素は $a$ です。$a$ に対応するコマンドは $insert$ なので、$insert$ と出力します。そして、バッファーから $a$ を削除します。

クエリ$IN$で $c$ というキーが入力されたので、バッファーに格納します。

クエリ$OUT$でバッファーの先頭から一つ取り出してコマンドを出力します。現時点のバッファーは ${ b, c }$ となっているので先頭の要素は $b$ です。$b$ に対応するコマンドは $delete$ なので、$delete$ と出力します。そして、バッファーから $b$ を削除します。

クエリ$OUT$でバッファーの先頭から一つ取り出してコマンドを出力します。現時点のバッファーは ${ c }$ となっているので先頭の要素は $c$ です。$c$ に対応するコマンドは $print$ なので、$print$ と出力します。そして、バッファーから $c$ を削除します。

クエリ$OUT$でバッファーの先頭から一つ取り出してコマンドを出力します。現時点のバッファーは空になっているので先頭の要素はありません。よって、$0$ と出力します。

入力例2

1
a insert
2
IN b
OUT

出力例2

-1