{"raw_statement":[{"iden":"statement","content":"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.\n\nThis \"personal treasure\" is a multiset $S$ of $m$ \"_01-strings_\".\n\nA \"_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.\n\n**Note that the multiset $S$ can contain equal elements.**\n\nFrequently, 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$.\n\nMrs. 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$.\n\nFor 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$.\n\nYou 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$."},{"iden":"input","content":"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.\n\nThe 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.\n\nEach of the next $m$ lines contains the \"_01-string_\" $s$ of length $n$ — the string in the multiset $S$.\n\nEach of the next $q$ lines contains the \"_01-string_\" $t$ of length $n$ and integer $k$ ($0\\leq k\\leq 100$) — the query."},{"iden":"output","content":"For each query, print the answer for this query."},{"iden":"examples","content":"Input\n\n2 4 5\n40 20\n01\n01\n10\n11\n00 20\n00 40\n11 20\n11 40\n11 60\n\nOutput\n\n2\n4\n2\n3\n4\n\nInput\n\n1 2 4\n100\n0\n1\n0 0\n0 100\n1 0\n1 100\n\nOutput\n\n1\n2\n1\n2"},{"iden":"note","content":"In the first example, we can get:\n\n\"_Wu_\" of (\"_01_\", \"_00_\") is $40$.\n\n\"_Wu_\" of (\"_10_\", \"_00_\") is $20$.\n\n\"_Wu_\" of (\"_11_\", \"_00_\") is $0$.\n\n\"_Wu_\" of (\"_01_\", \"_11_\") is $20$.\n\n\"_Wu_\" of (\"_10_\", \"_11_\") is $40$.\n\n\"_Wu_\" of (\"_11_\", \"_11_\") is $60$.\n\nIn the first query, pairs (\"_11_\", \"_00_\") and (\"_10_\", \"_00_\") satisfy the condition since their \"_Wu_\" is not greater than $20$.\n\nIn the second query, all strings satisfy the condition.\n\nIn the third query, pairs (\"_01_\", \"_11_\") and (\"_01_\", \"_11_\") satisfy the condition. Note that since there are two \"_01_\" strings in the multiset, the answer is $2$, not $1$.\n\nIn the fourth query, since $k$ was increased, pair (\"_10_\", \"_11_\") satisfies the condition too.\n\nIn the fifth query, since $k$ was increased, pair (\"_11_\", \"_11_\") satisfies the condition too."}],"translated_statement":[{"iden":"statement","content":"Childan 正在编造一个传奇故事，并试图向 Kasoura 家出售他的赝品——一条具有强烈 \"_Wu_\" 感觉的项链。但 Mr. Kasoura 正在质疑 Childan 故事的真实性，因此他将提出几个关于 Childan 所谓的 \"个人宝藏\" 项链的问题。\n\n这个 \"个人宝藏\" 是一个包含 $m$ 个 \"_01-字符串_\" 的多重集 $S$。\n\n一个 \"_01-字符串_\" 是一个包含 $n$ 个字符 \"_0_\" 和 \"_1_\" 的字符串。例如，当 $n = 4$ 时，字符串 \"_0110_\"、\"_0000_\" 和 \"_1110_\" 是 \"_01-字符串_\"，但 \"_00110_\"（有 5 个字符，不是 4 个）和 \"_zero_\"（包含非法字符）不是。\n\n*注意：多重集 $S$ 可以包含相等的元素。*\n\n通常，Mr. Kasoura 会提供一个 \"_01-字符串_\" $t$，并询问 Childan：在多重集 $S$ 中，有多少个字符串 $s$，使得对 $(s, t)$ 的 \"_Wu_\" 值 *不大于* $k$？\n\nMrs. Kasoura 和 Mr. Kasoura 认为，如果 $s_i = t_i$（$1 lt.eq i lt.eq n$），则该字符对的 \"_Wu_\" 值为 $w_i$，否则为 $0$。一个 \"_01-字符串_\" 对的 \"_Wu_\" 值是所有字符对的 \"_Wu_\" 值之和。注意，每个 \"_01-字符串_\" 的长度均为 $n$。\n\n例如，若 $w = [ 4, 5, 3, 6 ]$，则 (\"_1001_\", \"_1100_\") 的 \"_Wu_\" 值为 $7$，因为这两个字符串仅在第一和第三位字符相等，所以 $w_1 + w_3 = 4 + 3 = 7$。\n\n你需要帮助 Childan 回答 Mr. Kasoura 的查询：即找出多重集 $S$ 中满足对 $(s, t)$ 的 \"_Wu_\" 值不大于 $k$ 的字符串数量。\n\n第一行包含三个整数 $n$, $m$, $q$（$1 lt.eq n lt.eq 12$，$1 lt.eq q, m lt.eq 5 dot.op 10^5$）—— \"_01-字符串_\" 的长度、多重集 $S$ 的大小和查询次数。\n\n第二行包含 $n$ 个整数 $w_1, w_2, dots.h, w_n$（$0 lt.eq w_i lt.eq 100$）——第 $i$ 个字符的权重。\n\n接下来的 $m$ 行，每行包含一个长度为 $n$ 的 \"_01-字符串_\" $s$ —— 多重集 $S$ 中的字符串。\n\n接下来的 $q$ 行，每行包含一个长度为 $n$ 的 \"_01-字符串_\" $t$ 和一个整数 $k$（$0 lt.eq k lt.eq 100$）—— 一个查询。\n\n对于每个查询，请输出该查询的答案。\n\n在第一个例子中，我们可以得到：\n\n(\"_01_\", \"_00_\") 的 \"_Wu_\" 值为 $40$。\n\n(\"_10_\", \"_00_\") 的 \"_Wu_\" 值为 $20$。\n\n(\"_11_\", \"_00_\") 的 \"_Wu_\" 值为 $0$。\n\n(\"_01_\", \"_11_\") 的 \"_Wu_\" 值为 $20$。\n\n(\"_10_\", \"_11_\") 的 \"_Wu_\" 值为 $40$。\n\n(\"_11_\", \"_11_\") 的 \"_Wu_\" 值为 $60$。\n\n在第一个查询中，对 (\"_11_\", \"_00_\") 和 (\"_10_\", \"_00_\") 满足条件，因为它们的 \"_Wu_\" 值不大于 $20$。\n\n在第二个查询中，所有字符串都满足条件。\n\n在第三个查询中，对 (\"_01_\", \"_11_\") 和 (\"_01_\", \"_11_\") 满足条件。注意：由于多重集中有两个 \"_01_\" 字符串，答案是 $2$，而不是 $1$。\n\n在第四个查询中，由于 $k$ 增大，对 (\"_10_\", \"_11_\") 也满足条件。\n\n在第五个查询中，由于 $k$ 增大，对 (\"_11_\", \"_11_\") 也满足条件。"},{"iden":"input","content":"第一行包含三个整数 $n$, $m$, $q$（$1 lt.eq n lt.eq 12$，$1 lt.eq q, m lt.eq 5 dot.op 10^5$）—— \"_01-字符串_\" 的长度、多重集 $S$ 的大小和查询次数。第二行包含 $n$ 个整数 $w_1, w_2, dots.h, w_n$（$0 lt.eq w_i lt.eq 100$）——第 $i$ 个字符的权重。接下来的 $m$ 行，每行包含一个长度为 $n$ 的 \"_01-字符串_\" $s$ —— 多重集 $S$ 中的字符串。接下来的 $q$ 行，每行包含一个长度为 $n$ 的 \"_01-字符串_\" $t$ 和一个整数 $k$（$0 lt.eq k lt.eq 100$）—— 一个查询。"},{"iden":"output","content":"对于每个查询，请输出该查询的答案。"},{"iden":"examples","content":"输入\n2 4 5\n40 20\n01\n01\n10\n11\n00 20\n00 40\n11 20\n11 40\n11 60\n\n输出\n2\n4\n2\n3\n4\n\n输入\n1 2 4\n100\n0\n1\n0 0\n0 100\n1 0\n1 100\n\n输出\n1\n2\n1\n2"},{"iden":"note","content":"在第一个例子中，我们可以得到：\n\"_Wu_\" of (\"_01_\", \"_00_\") 是 $40$。\n\"_Wu_\" of (\"_10_\", \"_00_\") 是 $20$。\n\"_Wu_\" of (\"_11_\", \"_00_\") 是 $0$。\n\"_Wu_\" of (\"_01_\", \"_11_\") 是 $20$。\n\"_Wu_\" of (\"_10_\", \"_11_\") 是 $40$。\n\"_Wu_\" of (\"_11_\", \"_11_\") 是 $60$。\n\n在第一个查询中，对 (\"_11_\", \"_00_\") 和 (\"_10_\", \"_00_\") 满足条件，因为它们的 \"_Wu_\" 值不大于 $20$。\n\n在第二个查询中，所有字符串都满足条件。\n\n在第三个查询中，对 (\"_01_\", \"_11_\") 和 (\"_01_\", \"_11_\") 满足条件。注意：由于多重集中有两个 \"_01_\" 字符串，答案是 $2$，而不是 $1$。\n\n在第四个查询中，由于 $k$ 增大，对 (\"_10_\", \"_11_\") 也满足条件。\n\n在第五个查询中，由于 $k$ 增大，对 (\"_11_\", \"_11_\") 也满足条件。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m, q \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 12 $, $ 1 \\leq m, q \\leq 5 \\cdot 10^5 $.  \nLet $ w = (w_1, w_2, \\dots, w_n) \\in \\mathbb{Z}^n $ be the weight vector, where $ 0 \\leq w_i \\leq 100 $.  \nLet $ S $ be a multiset of $ m $ binary strings of length $ n $, i.e., $ S \\subseteq \\{0,1\\}^n $ with multiplicity.  \nFor any two strings $ s, t \\in \\{0,1\\}^n $, define the **Wu value** as:  \n$$\n\\text{Wu}(s, t) = \\sum_{i=1}^n w_i \\cdot \\mathbf{1}_{s_i = t_i}\n$$\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 12 $  \n2. $ 1 \\leq m, q \\leq 5 \\cdot 10^5 $  \n3. $ 0 \\leq w_i \\leq 100 $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. $ 0 \\leq k \\leq 100 $ for each query  \n\n**Objective**  \nFor each query $ (t, k) $, compute:  \n$$\n\\sum_{s \\in S} \\mathbf{1}_{\\text{Wu}(s, t) \\leq k}\n$$  \nThat is, count the number of strings $ s \\in S $ (with multiplicity) such that the Wu value of the pair $ (s, t) $ is at most $ k $.","simple_statement":null,"has_page_source":false}