English · Original
Chinese · Translation
Formal · Original
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$.
## Input
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.
## Output
For each query, print the answer for this query.
[samples]
## Note
In the first example, we can get:
"_Wu_" of ("_01_", "_00_") is $40$.
"_Wu_" of ("_10_", "_00_") is $20$.
"_Wu_" of ("_11_", "_00_") is $0$.
"_Wu_" of ("_01_", "_11_") is $20$.
"_Wu_" of ("_10_", "_11_") is $40$.
"_Wu_" of ("_11_", "_11_") is $60$.
In the first query, pairs ("_11_", "_00_") and ("_10_", "_00_") satisfy the condition since their "_Wu_" is not greater than $20$.
In the second query, all strings satisfy the condition.
In 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$.
In the fourth query, since $k$ was increased, pair ("_10_", "_11_") satisfies the condition too.
In the fifth query, since $k$ was increased, pair ("_11_", "_11_") satisfies the condition too.
Childan 正在编造一个传奇故事，并试图向 Kasoura 家出售他的赝品——一条具有强烈 "_Wu_" 感觉的项链。但 Mr. Kasoura 正在质疑 Childan 故事的真实性，因此他将提出几个关于 Childan 所谓的 "个人宝藏" 项链的问题。
这个 "个人宝藏" 是一个包含 $m$ 个 "_01-字符串_" 的多重集 $S$。
一个 "_01-字符串_" 是一个包含 $n$ 个字符 "_0_" 和 "_1_" 的字符串。例如，当 $n = 4$ 时，字符串 "_0110_"、"_0000_" 和 "_1110_" 是 "_01-字符串_"，但 "_00110_"（有 5 个字符，不是 4 个）和 "_zero_"（包含非法字符）不是。
*注意：多重集 $S$ 可以包含相等的元素。*
通常，Mr. Kasoura 会提供一个 "_01-字符串_" $t$，并询问 Childan：在多重集 $S$ 中，有多少个字符串 $s$，使得对 $(s, t)$ 的 "_Wu_" 值 *不大于* $k$？
Mrs. Kasoura 和 Mr. Kasoura 认为，如果 $s_i = t_i$（$1 lt.eq i lt.eq n$），则该字符对的 "_Wu_" 值为 $w_i$，否则为 $0$。一个 "_01-字符串_" 对的 "_Wu_" 值是所有字符对的 "_Wu_" 值之和。注意，每个 "_01-字符串_" 的长度均为 $n$。
例如，若 $w = [ 4, 5, 3, 6 ]$，则 ("_1001_", "_1100_") 的 "_Wu_" 值为 $7$，因为这两个字符串仅在第一和第三位字符相等，所以 $w_1 + w_3 = 4 + 3 = 7$。
你需要帮助 Childan 回答 Mr. Kasoura 的查询：即找出多重集 $S$ 中满足对 $(s, t)$ 的 "_Wu_" 值不大于 $k$ 的字符串数量。
第一行包含三个整数 $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$）—— 一个查询。
对于每个查询，请输出该查询的答案。
在第一个例子中，我们可以得到：
("_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$ 增大，对 ("_10_", "_11_") 也满足条件。
在第五个查询中，由于 $k$ 增大，对 ("_11_", "_11_") 也满足条件。
## Input
第一行包含三个整数 $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$）—— 一个查询。
## Output
对于每个查询，请输出该查询的答案。
[samples]
## Note
在第一个例子中，我们可以得到：
"_Wu_" of ("_01_", "_00_") 是 $40$。
"_Wu_" of ("_10_", "_00_") 是 $20$。
"_Wu_" of ("_11_", "_00_") 是 $0$。
"_Wu_" of ("_01_", "_11_") 是 $20$。
"_Wu_" of ("_10_", "_11_") 是 $40$。
"_Wu_" of ("_11_", "_11_") 是 $60$。
在第一个查询中，对 ("_11_", "_00_") 和 ("_10_", "_00_") 满足条件，因为它们的 "_Wu_" 值不大于 $20$。
在第二个查询中，所有字符串都满足条件。
在第三个查询中，对 ("_01_", "_11_") 和 ("_01_", "_11_") 满足条件。注意：由于多重集中有两个 "_01_" 字符串，答案是 $2$，而不是 $1$。
在第四个查询中，由于 $k$ 增大，对 ("_10_", "_11_") 也满足条件。
在第五个查询中，由于 $k$ 增大，对 ("_11_", "_11_") 也满足条件。
**Definitions**
Let $ n, m, q \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 12 $, $ 1 \leq m, q \leq 5 \cdot 10^5 $.
Let $ w = (w_1, w_2, \dots, w_n) \in \mathbb{Z}^n $ be the weight vector, where $ 0 \leq w_i \leq 100 $.
Let $ S $ be a multiset of $ m $ binary strings of length $ n $, i.e., $ S \subseteq \{0,1\}^n $ with multiplicity.
For any two strings $ s, t \in \{0,1\}^n $, define the **Wu value** as:
$$
\text{Wu}(s, t) = \sum_{i=1}^n w_i \cdot \mathbf{1}_{s_i = t_i}
$$
**Constraints**
1. $ 1 \leq n \leq 12 $
2. $ 1 \leq m, q \leq 5 \cdot 10^5 $
3. $ 0 \leq w_i \leq 100 $ for all $ i \in \{1, \dots, n\} $
4. $ 0 \leq k \leq 100 $ for each query
**Objective**
For each query $ (t, k) $, compute:
$$
\sum_{s \in S} \mathbf{1}_{\text{Wu}(s, t) \leq k}
$$
That 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 $.
API Response (JSON)
{
"problem": {
"name": "D. The Wu",
"description": {
"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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1017D"
},
"statements": [
{
"statement_type": "Markdown",
"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 ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Childan 正在编造一个传奇故事，并试图向 Kasoura 家出售他的赝品——一条具有强烈 \"_Wu_\" 感觉的项链。但 Mr. Kasoura 正在质疑 Childan 故事的真实性，因此他将提出几个关于 Childan 所谓的 \"个人宝藏\" 项链的问题。\n\n这个 \"个人宝藏\" 是一个包含 $m$ 个 \"_01-字符串_\" 的多重集 $S$。\n\n一个 \"_01-字符串_\" 是一个包含 $n$...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**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 \\...",
"is_translate": false,
"language": "Formal"
}
]
}