A11883 | The Wu

Childan is making up a legendary story and trying to sell his forgery — a necklace with a strong sense of "Wu" to the Kasouras. But Mr. Kasoura is challenging the truth of Childan's story. So he is going to ask a few questions about Childan's so-called "personal treasure" necklace.

This "personal treasure" is a multiset $S$ of $m$ "01-strings".

A "01-string" is a string that contains $n$ characters "0" and "1". For example, if $n=4$ , strings "0110", "0000", and "1110" are "01-strings", but "00110" (there are $5$ characters, not $4$ ) and "zero" (unallowed characters) are not.

Note that the multiset $S$ can contain equal elements.

Frequently, Mr. Kasoura will provide a "01-string" $t$ and ask Childan how many strings $s$ are in the multiset $S$ such that the "Wu" value of the pair $(s, t)$ is not greater than $k$ .

Mrs. Kasoura and Mr. Kasoura think that if $s_i = t_i$ ( $1\leq i\leq n$ ) then the "Wu" value of the character pair equals to $w_i$ , otherwise $0$ . The "Wu" value of the "01-string" pair is the sum of the "Wu" values of every character pair. Note that the length of every "01-string" is equal to $n$ .

For example, if $w=[4, 5, 3, 6]$ , "Wu" of ("1001", "1100") is $7$ because these strings have equal characters only on the first and third positions, so $w_1+w_3=4+3=7$ .

You need to help Childan to answer Mr. Kasoura's queries. That is to find the number of strings in the multiset $S$ such that the "Wu" value of the pair is not greater than $k$ .

The first line contains three integers $n$ , $m$ , and $q$ ( $1\leq n\leq 12$ , $1\leq q, m\leq 5\cdot 10^5$ ) — the length of the "01-strings", the size of the multiset $S$ , and the number of queries.

The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ( $0 \le w_i \le 100$ ) — the value of the $i$ -th caracter.

Each of the next $m$ lines contains the "01-string" $s$ of length $n$ — the string in the multiset $S$ .

Each of the next $q$ lines contains the "01-string" $t$ of length $n$ and integer $k$ ( $0\leq k\leq 100$ ) — the query.

For each query, print the answer for this query.