辞書をこよなく愛する者がいた。彼らは自分だけの辞書を作ることが大好きである。 そこであなたは彼らの辞書に、自由にカスタマイズする機能を付け加えてあげることにした。
初めに、何の単語も入っていない空の辞書が存在する。 N個の文字列SidとQ個のクエリが与えられる。 各クエリはクエリの種類kと文字列を指すidで与えられる。 クエリの種類は以下の3つである。
各クエリに答えるプログラムを書いてほしい。
注意: 入力のサイズが大きいので高速な入力に対応する形式を推奨する。
入力は以下の形式で与えられる。
N S1 S2 . . . SN Q k1 id1 k2 id2 . . . kQ idQ
1行目に、1つの整数Nが与えられる。2行目からN+1行に、N個の文字列Sidが与えられる。 N+2行目にクエリの数Qが与えられ、続くQ行に各クエリの種類を表すkと文字列を指すidが与えれる。
クエリごとに解答を一行に出力せよ。
3 apple app banana 9 1 1 3 1 3 2 3 3 2 1 1 2 3 1 3 2 3 3
1 1 -1 -1 2 -1
7 aaaab aaa aaaa aaaaaabc abbbbbc ab abbb 13 1 1 3 2 1 4 3 2 1 3 3 2 2 3 3 3 1 5 1 7 3 6 2 5 3 6
1 4 3 4 7 7