奇尔丹正在编造一个传奇故事,并试图向卡苏拉斯夫妇出售他的赝品——一条带有强烈“Wu”字样的项链。但卡苏拉先生正在挑战齐尔丹故事的真实性。所以他要问几个关于Childan所谓的“私人宝藏”项链的问题。
这个“个人宝藏”是 $$$S$$$ $$$m$$$“01-strings”的多重集合。
“01-string”是包含 $$$n$$$ 字符“0”和“1”的字符串。例如,如果 $$$n=4$$$,则字符串“0110”、“0000”和“1110”是“01 字符串”,但“00110”(有 $$$5$$$ 字符,而不是 $$$4$$$)和“零”(不允许的字符)则不是。
请注意,多重集 $$$S$$$ 可以包含相等的元素。
Kasoura 先生经常会提供“01 字符串”$$$t$$$ 并询问 Childan 多重集合 $$$S$$$ 中有多少个字符串 $$$s$$$,使得 $$$(s, t)$$$ 对的“Wu”值不大于 $$$k$$$。
Kasoura女士和Kasoura先生认为如果$$$s_i = t_i$$$ ($$$1\leq i\leq n$$$) 则字符对的“Wu”值等于$$$w_i$$$,否则$$$0$$$。 “01-string”对的“Wu”值是每个字符对的“Wu”值之和。请注意,每个“01 字符串”的长度等于 $$$n$$$。
例如,如果 $$$w=[4, 5, 3, 6]$$$,则 ("1001", "1100") 的 "Wu" 为 $$$7$$$,因为这些字符串仅在第一个和第三个位置上具有相同的字符,因此 $$$w_1+w_3=4+3=7$$$。
你需要帮助Childan回答Kasoura先生的疑问。即找到多重集合 $$$S$$$ 中使得该对的“Wu”值不大于 $$$k$$$ 的字符串数量。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1\leq n\leq 12$$$, $$$1\leq q, m\leq 5\cdot 10^5$$$) - “01-strings”的长度,多重集 $$$S$$$ 的大小,以及查询的数量。
第二行包含 $$$n$$$ 整数 $$$w_1, w_2, \ldots, w_n$$$ ($$$0 \le w_i \le 100$$$) — 第 $$$i$$$ 个字符的值。
接下来的 $$$m$$$ 行均包含长度为 $$$n$$$ 的“01 字符串”$$$s$$$ — 多重集 $$$S$$$ 中的字符串。
接下来的 $$$q$$$ 行包含长度为 $$$n$$$ 的“01 字符串”$$$t$$$ 和整数 $$$k$$$ ($$$0\leq k\leq 100$$$) — 查询。
输出
对于每个查询,打印该查询的答案。
示例
输入 #1
2 4 5 40 20 01 01 10 11 00 20 00 40 11 20 11 40 11 60
输出 #1
2 4 2 3 4
输入 #2
1 2 4 100 0 1 0 0 0 100 1 0 1 100
输出 #2
1 2 1 2
注意
在第一个例子中,我们可以得到:
(“01”,“00”)的“Wu”是$$$40$$$。
(“10”,“00”)的“Wu”是$$$20$$$。
(“11”,“00”)的“Wu”是$$$0$$$。
(“01”,“11”)的“Wu”是$$$20$$$。
("10", "11") 的 "Wu" 是 $$$40$$$。
("11", "11") 的 "Wu" 是 $$$60$$$。
在第一个查询中,对 ("11", "00") 和 ("10", "00") 满足条件,因为它们的 "Wu" 不大于 $$$20$$$。
在第二个查询中,所有字符串都满足条件。
在第三个查询中,对 (“01”, “11”) 和 (“01”, “11”) 满足条件。请注意,由于多重集中有两个“01”字符串,因此答案是 $$$2$$$,而不是 $$$1$$$。
在第四个查询中,由于 $$$k$$$ 增加了,pair ("10", "11") 也满足条件。
In the fifth query, since $$$k$$$ was increased, pair ("11", "11") satisfies the condition too.