Xiao I runs an arcade, and a newly introduced slot machine has become very popular. As the operator, Xiao I first needs to set the state of the slot machine. The state of the slot machine is a triple $(l, S, \mathbf{p})$, where:

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

Once the state is set, the game can begin. The process of each round of the game is as follows:

• The player first obtains the state of the slot machine $(l, S, \mathbf{p})$.
• The slot machine internally selects a string $s \in S$ as the answer string. The player needs to interact with the slot machine several times to obtain the answer string.
  • In each interaction, the player inserts a game coin and pulls the lever of the slot machine. Then, an information string $t$ of length $l$ appears on the interface of the slot machine. For $0 \le i \le l-1$, $t_i$ is equal to $s_i$ with probability $p_i$, and is equal to $?$ with probability $(1 - p_i)$.
  • All random processes that generate information strings during the interaction are mutually independent.
• When the player can uniquely determine the answer string based on the state of the slot machine and the several information strings obtained, they can input the answer string into the slot machine to end the game and receive a reward.

Xiao I has set a state but does not yet know how much reward to set. To match the reward with the difficulty, Xiao I wants to know: for each string $t \in S$, assuming the player plays with an optimal strategy (i.e., ending the game as soon as the answer string can be uniquely determined), if the answer string is $t$, what is the expected number of game coins the player needs to insert?

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

Input

Read data from standard input. There are multiple test cases. The first line contains an integer $T$ representing the number of test cases. Then, each test case is input sequentially. For each test case: The first line contains two integers $l$ and $n$, representing the length of the strings 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 binary string $s_i$ of length $l$, describing a string in $S$.

Output

Output to standard output. For each test case, output $n$ lines. The $i$-th line represents the expected number of game coins the player needs to insert under the optimal strategy when the answer string is $s_i$, modulo $998244353$. It is easy to prove that under the problem constraints, this value always exists in the modular sense.

Examples

Input 1

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

Output 1

2
2
10000
1
10000
0
209031157
194428714
835313860
674719626

Note

• For the first test case, each interaction has 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 game coins is $\sum_{i=1}^{\infty} \frac{i}{2^i} = 2$.
• For the second test case, each interaction can obtain the second bit of the string, and there is a probability of $\frac{1}{10000}$ to obtain the first bit of the string. When the second string is the answer, it can be uniquely determined by the second bit of the string, while for the other two strings, the first bit of the string must be obtained.
• For the third test case, since $|S| = 1$, the answer string can be determined without any interaction.
• For the fourth test case, I have a marvelous explanation, but the space here is too small to contain it.

Constraints

For all test cases, $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 distinct binary strings of length $l$.