Inflation is rampant in Byteotia, and a worried Baltazar is wondering how to invest his money. Unfortunately, he has just seen an advertisement for bookmaking bets and has decided to invest in them.

There will soon be $n$ football matches, each of which will end with the victory of one of the sides (there are no draws). A single bet consists of predicting the outcome of each of the $n$ matches. The winnings for correctly predicting the outcome of the $i$-th match are $a_i$ bajtalars if the first team wins, and $b_i$ bajtalars if the second team wins. An incorrect prediction of a match outcome yields no winnings. The winnings of a bet are the sum of the winnings associated with all predicted outcomes.

Baltazar wants to buy one of the available bets. The $i$-th bet has a fixed sequence $p_i$ of length $n$, which describes the predicted outcome of each match, as well as a price $k_i$ bajtalars; the $j$-th element of the sequence $p_i$, denoted $p_{i,j}$, is equal to $0$ if the predicted outcome of the $j$-th match is a victory for the first team, and $1$ otherwise. The profit of a bet is defined as its winnings minus its price.

Baltazar has given you information about all available bets. Now he asks you to answer $q$ questions that concern him. In the $i$-th question, you receive a sequence $w_i$ describing the actual outcomes of each of the $n$ matches; the $j$-th element of the sequence $w_i$, denoted $w_{i,j}$, is equal to $0$ if the outcome of the $j$-th match is a victory for the first team, and $1$ otherwise. Your task is to determine the maximum profit that can be obtained using one of the given bets if the results of all $n$ matches are described by the given sequence $w_i$. Additionally, you should determine the number of given bets that achieve this maximum profit.

Input

The first line of input contains a single integer $n$ ($1 \le n \le 20$), representing the number of matches. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$). The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($0 \le b_i \le 10^9$). The fourth line contains a single integer $z$ ($1 \le z \le 10^6$), representing the number of bets. Each of the next $z$ lines contains the description of the $i$-th bet. This description consists of a sequence $p_i$ (a string of $n$ characters, either $0$ or $1$, with no spaces) and an integer $k_i$ ($0 \le k_i \le 10^9$). The next line contains a single integer $q$ ($1 \le q \le 10^6$), representing the number of questions. Each of the next $q$ lines contains the description of the $i$-th question, which is a sequence $w_i$ (a string of $n$ characters, either $0$ or $1$, with no spaces).

Output

The output should consist of $q$ lines. The $i$-th line of the output should contain two integers representing the answer to the $i$-th question. The first should be equal to the maximum profit that can be obtained using one of the given bets if the match results are described by the sequence $w_i$. The second should be equal to the number of given bets that achieve this maximum profit.

Examples

Input 1

3
1 3 5
4 2 5
5
000 5
010 2
101 1
000 8
011 3
3
000
011
100

Output 1

4 2
5 1
6 1

Note

Explanation of the example: We have $a_1 = 1, a_2 = 3, a_3 = 5, b_1 = 4, b_2 = 2, b_3 = 5$. The sequences of predicted match outcomes for the individual bets are: $p_1 = 000, p_2 = 010, p_3 = 101, p_4 = 000, p_5 = 011$, and their prices are $k_1 = 5, k_2 = 2, k_3 = 1, k_4 = 8, k_5 = 3$. In the first question, the sequence describing the match results is $w_1 = 000$. Here are the profits that can be obtained in this question using the individual bets: first bet: $a_1 + a_2 + a_3 - k_1 = 4$, second bet: $a_1 + a_3 - k_2 = 4$, third bet: $a_2 - k_3 = 2$, fourth bet: $a_1 + a_2 + a_3 - k_4 = 1$, * fifth bet: $a_1 - k_5 = -2$.

The maximum profit ($4$) can thus be obtained using the first or second bet. The sequence describing the match results in the second question is $w_2 = 011$. In this case, bet $5$ is the only one that gives the maximum profit equal to $a_1 + b_2 + b_3 - k_5 = 5$. The sequence describing the match results in the third question is $w_3 = 100$. In this case, bet $3$ is the only one that gives the maximum profit equal to $b_1 + a_2 - k_3 = 6$.

Subtasks

If your program correctly outputs only the first values of the result pairs, while the second numbers fit into a 32-bit signed integer type (int), you will receive 50% of the points for that test.