← 返回题目列表

Codeforces · 1017/D

D. 吴

中文机器翻译题面 查看原题

奇尔丹正在编造一个传奇故事,并试图向卡苏拉斯夫妇出售他的赝品——一条带有强烈“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.