Problem E: Distinct Dictionary

Background

辞書をこよなく愛する者がいた。彼らは自分だけの辞書を作ることが大好きである。 そこであなたは彼らの辞書に、自由にカスタマイズする機能を付け加えてあげることにした。

Problem

初めに、何の単語も入っていない空の辞書が存在する。 N個の文字列S_idとQ個のクエリが与えられる。 各クエリはクエリの種類kと文字列を指すidで与えられる。 クエリの種類は以下の3つである。

• k=1のときS_idを辞書に追加する。
• k=2のときS_idを辞書から削除する。
• k=3のとき辞書に追加された文字列の中でS_idを先頭からの部分文字列に含み且つ辞書順最小の文字列のidを出力する。無い場合は-1を出力する。

各クエリに答えるプログラムを書いてほしい。

注意： 入力のサイズが大きいので高速な入力に対応する形式を推奨する。

Input

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

N
S1
S2
.
.
.
SN
Q
k1 id1
k2 id2
.
.
.
kQ idQ

1行目に、1つの整数Nが与えられる。2行目からN+1行に、N個の文字列S_idが与えられる。 N+2行目にクエリの数Qが与えられ、続くQ行に各クエリの種類を表すkと文字列を指すidが与えれる。

Constraints

• 文字列は全て異なる。
• N個の文字列S_idの長さの合計は10⁶を超えない。
• 既に辞書に追加されている文字列が再び追加されるような入力は存在しない。
• 辞書に追加されていない文字列を削除するような入力は存在しない。
• 与えられる文字列に含まれる文字は英小文字のみである。
• 1 ≤ N ≤ 10⁵
• 1 ≤ id ≤ N
• 1 ≤ Q ≤ 10⁵
• 1 ≤ |S_id| ≤ 10⁵ (ただし、|s|は文字列sの長さを表す。)

Output

クエリごとに解答を一行に出力せよ。

Sample Input1

3
apple
app
banana
9
1 1
3 1
3 2
3 3
2 1
1 2
3 1
3 2
3 3

Sample Output1

1
1
-1
-1
2
-1

Sample Input2

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

Sample Output2

1
4
3
4
7
7