Problem Description

Xiao I runs an arcade, and a new type of slot machine has recently become very popular.

As the operator, Xiao I first needs to set the state of the slot machine. The state is a triple $(l,S,\mathbf{p})$, where:

• $l$ is a positive integer.
• $S$ is a non-empty set of strings, where every string is a length-$l$ binary string.
• $\mathbf{p}$ is a length-$l$ real sequence $p_0,p_1,\dots,p_{l-1}$, where for any $0 \le i \le l - 1$, $0 < p_i \le 1$.

After setting the state, the game can start. Each round of the game works as follows:

• The player first obtains the slot machine state $(l,S,\mathbf{p})$.
• Internally, the slot machine chooses a string $s \in S$ as the answer string. The player needs to obtain the answer string through several interactions with the machine.
  • In each interaction, the player inserts one coin and pulls the lever. Then the machine displays an information string $t$ of length $l$. For $0 \le i \le l - 1$, $t_i$ equals $s_i$ with probability $p_i$, and equals ? with probability $(1-p_i)$.
  • All random processes used to generate information strings during interactions are pairwise independent.
• Once the player can uniquely determine the answer string based on the slot machine state and the information strings obtained from interactions, they may input the answer string into the machine to end the game and receive the reward.

Xiao I has set a state, but has not decided how large the reward should be. To match the reward with the difficulty, Xiao I wants to know: for each string $t$ in $S$, if the player plays with an optimal strategy (that is, they end the game as soon as the answer string can be uniquely determined), and the answer string is $t$, what is the expected number of coins the player needs to insert.

Since Xiao I does not like real numbers, you need to output the answer modulo $998244353$.

Input Format

This problem has multiple test cases. The first line contains an integer $T$ indicating the number of test cases, followed by the input for each test case.

For each test case:

• The first line contains two integers $l,n$, denoting the string length and the size of $S$.
• The second line contains $l$ integers $c_0,c_1,\dots,c_{l-1}$, where $p_i = \frac{c_i}{10^4}$.
• The next $n$ lines each contain a length-$l$ binary string $s_i$, describing a string in $S$.

Output Format

For each test case, output $n$ lines. The $i$-th line should be the expected number of coins the player needs to insert when the answer string is $s_i$ under the optimal strategy, modulo $998244353$. The problem guarantees that this value always exists in the modular sense.

4
1 2
5000
0
1
2 3
1 10000
00
01
10
1 1
1
1
3 4
8888 7777 5555
000
010
101
110

2
2
10000
1
10000
0
209031157
194428714
835313860
674719626

Hint

[Sample Explanation #1]

• For the first test case, in each interaction there is a probability of $\frac{5000}{10000} = \frac{1}{2}$ to know whether the answer string is $0$ or $1$, and a probability of $\frac{1}{2}$ to obtain no information. Therefore the expected number of coins is $\sum_{i=1}^{+\infty} \frac{i}{2^i} = 2$.
• For the second test case, in each interaction you can always obtain the second bit of the string, and you obtain the first bit with probability $\frac{1}{10000}$. When the second string is the answer string, it can be uniquely determined by the second bit, while for the other two strings, you must obtain the first bit.
• For the third test case, since $|S| = 1$, no interaction is needed to determine the answer string.
• For the fourth test case, I have a brilliant explanation, but this space is too small to write it down.

[Constraints]

For all testdata, $1 \le T \le 10$, $1 \le l \le 15$, $1 \le n \le 2^l$, $1 \le c_i \le 10^4$, and $s_1,\dots,s_n$ are pairwise distinct length-$l$ binary strings.

[Afterword]

“Hey, hey, hey, minors are not allowed to enter the arcade! What? You say you want to go in to learn competitive programming algorithms? Who would believe that nonsense!”

[Source]

From the finals of the 2023 Tsinghua University Student Programming Contest and Collegiate Invitational (THUPC2023).

Solutions and other resources can be found at https://github.com/THUSAAC/THUPC2023.

Translated by ChatGPT 5