Little X and Little Y are both string masters. As string masters, they decide to play a game to determine who is better. One day, they select $k$ binary strings and measure their "beauty," where the $i$-th binary string $t_i$ has a beauty value of $v_i$. (Note: $v_i$ may be negative.)

They initially select a binary string $S$ and take turns appending either a $0$ or a $1$ to the end of $S$, with Little X going first. After a player appends a character, if any $t_i$ becomes a substring of $S$ for the first time, that player receives points equal to the sum of the beauty values of these binary strings.

The game ends when all $t_i$ have become substrings of $S$. Both Little X and Little Y wish to maximize their own score minus their opponent's score at the end of the game.

You may have noticed that in some cases, the game might never end. Therefore, Little X and Little Y have added a draw mechanism: if a player believes that continuing the game will not increase their net gain (i.e., their score minus the opponent's score), they will propose a draw. If both players propose a draw, the game ends immediately.

Little X and Little Y are equally skilled at manipulating strings, and the choice of the initial string $S$ may affect the fairness of the game. Thus, they have prepared $q$ binary strings $S_1, S_2, \dots, S_q$ and have come to you, wanting to know the final value of Little X's score minus Little Y's score when the initial string is $S = S_i$, assuming both play optimally.

Input

The first line contains a positive integer $k$.

The next $k$ lines each contain a binary string and an integer. The $i$-th line represents $t_i$ and its beauty value $v_i$.

The next line contains a positive integer $q$.

The next $q$ lines each contain a binary string. The $i$-th line represents $S_i$.

Constraints: $1 \le k \le 18$, $1 \le q \le 524286$, $1 \le |t_i| \le 8$, $1 \le |S_i| \le 18$, $|v_i| \le 10^5$.

Output

Output $q$ lines, where the $i$-th line is the value of Little X's score minus Little Y's score when $S = S_i$.

Examples

Input 1

3
11 1
0 2
000 3
2
0
1

Output 1

-1
3

Note

For Example 1:

• When $S$ is initially $0$: If Little X appends $0$ in the first step, then Little Y appends $0$, and $S$ becomes $000$. Little X's score minus Little Y's score is $0 - v_3 = -3$. It is easy to see that $v_1$ cannot be obtained by anyone subsequently. If Little X appends $1$ in the first step, then Little Y appends $1$, and $S$ becomes $011$. Little X's score minus Little Y's score is $0 - v_1 = -1$. It is easy to see that $v_3$ cannot be obtained by anyone subsequently. Therefore, the answer under optimal strategy is $-1$.
• When $S$ is initially $1$: One optimal strategy is for Little X to append $0$ in the first step. This is equivalent to the case where Little Y goes first with an initial string of $0$. Based on the discussion above, the answer under optimal strategy is $v_1 + v_2 = 3$.