Problem E: Distinct Dictionary

Background

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

Problem

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

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

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

Input

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

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が与えれる。

Constraints

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