Problem Statement

(Added at 22:29: If you are participating in a language other than C/C++ and handle strings as keys, we recommend storing them in a hash-based associative array rather than an ordinary associative array.)

Ame is once again going to help Yuki, the older sister who runs "Yukicoder".

Last time, Ame successfully managed to create the final standings of the contest, but many participants said, "We want to know our rank during the contest too."

So this time, Ame's job is to tally the contest results and, whenever a participant asks for their rank, to answer immediately.

The way scores are calculated and other details are the same as in Ame and Yuki of Yukicoder (2), so please refer to that problem as well.

Input

$N$
$L_1 \ L_2 \ ... \ L_N$
$T$
$Name_1 \ P_1$
$Name_2 \ P_2$
$:$
$Name_T \ P_T$

The first line contains the number of problems $N$.

The second line contains the level (number of ★) of each problem, $L_i \ (1 \leq i \leq N)$, separated by spaces.

The third line contains the number of submissions $T$.

The following $T$ lines, starting from the fourth line, contain the information of each submission in chronological order.

The $i \ (1 \leq i \leq T)$-th of these lines, counted from the fourth line, contains the submitter's name $Name_i$ and $P_i$, which is either the name of the submitted problem or '?', separated by a space.

If $P_i$ is an uppercase letter, this means that $Name_i$ solved problem $P_i$.

If $P_i$ is '?', this is a question query, and Ame must answer the current rank of $Name_i$.

The input satisfies the following constraints.

• $1 \leq N \leq 26$
• $1 \leq L_i \leq 6$
• $2 \leq T \leq 10^5$
• $1 \leq Length(Name_i) \leq 16, \ Name_i$ consists only of lowercase English letters
• $P_i$ is one of the letters from '$A$' to "the $N$-th uppercase letter", or '?'
• If ($i \neq j$ and $P_i \neq$ '?'), then $(Name_i, P_i) \neq (Name_j, P_j)$
• There exists at least one $i$ satisfying $P_i =$ '?'
• If $P_i =$ '?', there exists at least one $j$ satisfying ($Name_i = Name_j$ and $j < i$)

Output

$Rank_1$
$Rank_2$
$:$
$Rank_M$

Let $M$ be the number of times a rank is asked for. The output consists of $M$ lines.

Sample

2
2 2
5
ame A
yuki B
yuki ?
yuki A
ame ?

2
2

6
1 2 3 4 5 6
12
yopusot A
yusopot A
yopusot ?
yosoput C
yopusot B
yosoput ?
yosutop F
yusopot ?
yotupos D
yusopot ?
yosutop ?
yopusot ?

1
1
4
5
1
4

1
1
2
rian A
rian ?

1