Expected Coin Cost in a Slot Machine Game

Little I runs an arcade and has recently introduced a new type of slot machine that is very popular. The machine is configured by a state \((l, S, \mathbf{p})\) where:

• \(l\) is a positive integer,
• \(S\) is a non‐empty set of binary strings (each of length \(l\));
• \(\mathbf{p}=(p_0,p_1,\dots,p_{l-1})\) is a sequence of real numbers with \(0<p_i\le 1\) for \(0\le i<l\).

After the state is set, a game round proceeds as follows:

1. The player is informed of the state \((l,S,\mathbf{p})\).
2. The machine secretly chooses an answer string \(s\) from \(S\). The player may interact with the machine repeatedly to deduce \(s\). In each interaction, the player pays one coin and pulls the lever; then the machine displays an information string \(t\) of length \(l\). For every \(0\le i<l\), the character \(t_i\) is:
   • equal to \(s_i\) with probability \(p_i\), or
   • '?' with probability \(1-p_i\).
   All these random experiments are mutually independent.
3. The player collects all information strings gathered during the interactions. As soon as the revealed bits together with the known state \((l,S,\mathbf{p})\) uniquely determine the answer \(s\) (that is, there is exactly one string in \(S\) consistent with all revealed bits), the player may submit this answer to finish the game and claim a reward.

Assume that the player uses an optimal strategy (stopping at the first moment when the answer is uniquely determined). For every string \(t\) in \(S\) (when it is the answer), Little I wishes to know the expected number of coins the player must pay. Since Little I dislikes non‐integer numbers, you are to output the answer modulo \(998244353\).

Note on the solution: For a given answer string \(t\) and the other strings \(u\in S\setminus\{t\}\), the game stops when for every such \(u\) there is at least one position \(i\) (where \(t_i\neq u_i\)) whose content is revealed. If we denote \(D_{t,u}=\{i: t_i\neq u_i\}\) and define the random variable for the first revealed round in position \(i\) (which is geometrically distributed with parameter \(p_i\)), one may show that the expected number of rounds needed is given by the formula:

[ E[t]=\sum_{\emptyset\neq X\subseteq S\setminus{t}}(-1)^{|X|-1}\frac{1}{1-\prod_{i\in \bigcup_{u\in X}D_{t,u}}(1-p_i)}. ]

You are to compute this value modulo \(998244353\) for every \(t\in S\).

inputFormat

The first line contains two integers \(l\) and \(n\) \((1\le l\le ? ,\; 1\le n\le ? )\) -- the length of the strings and the size of the set \(S\) respectively.

The next \(n\) lines each contain a binary string of length \(l\) (the elements of \(S\)). It is guaranteed that they are all distinct.

The last line contains \(l\) real numbers \(p_0,p_1,\dots,p_{l-1}\) (each satisfying \(0<p_i\le 1\)).

outputFormat

Output \(n\) lines. The \(i\)th line should contain a single integer -- the expected number of coins the player must pay (modulo \(998244353\)) when the answer string is the \(i\)th string of \(S\) (in input order).

sample

3 1
010
1 1 1

0