Subset Convolution of Power Series

We define a subset power series \(F(x)\) and a polynomial \(G(x)\) as follows:

\[ F(x) = \sum_{S \subseteq [n]} f_S\, x^S \quad\text{and}\quad G(x) = \sum_{i=0}^{m} g_i\, x^i, \]

where the variables \(x^S\) are indexed by subsets \(S\) of \(\{1,2,\ldots,n\}\). The multiplication on these monomials is defined as subset convolution:

[ x^S \cdot x^T = \begin{cases} x^{S \cup T} & \text{if } S \cap T = \varnothing,
0 & \text{otherwise.} \end{cases} ]

Therefore, when expanding \(G(F(x))\), we have

[ G(F(x)) = \sum_{i=0}^{m} g_i, (F(x))^i, ]

where (F(x)^0) is defined as 1 for the empty set and 0 for every nonempty subset, and for (i \ge 1),

[ (F(x))^i [x^S] = \sum_{S_1 \uplus S_2 \uplus \cdots \uplus S_i = S} \prod_{j=1}^{i} f_{S_j}, ]

with (S_1, S_2, \ldots, S_i) being disjoint subsets whose union is (S).

Your task is to compute \([x^S]\,G(F(x))\) modulo 998244353 for every subset \(S \subseteq \{1,2,\ldots,n\}\). The subsets are represented by their bitmask order, starting from 0 (the empty set) to \(2^n-1\) (\(\{1,2,\ldots,n\}\)).

inputFormat

The input consists of three lines:

1. The first line contains two integers \(n\) and \(m\), where \(n\) is the number of elements in \(\{1,2,\ldots,n\}\) and \(m\) is the degree of the polynomial \(G(x)\).
2. The second line contains \(2^n\) integers representing \(f_S\) in order of increasing bitmask (i.e. from the empty set \(\varnothing\) to \(\{1,2,\ldots,n\}\)).
3. The third line contains \(m+1\) integers representing the coefficients \(g_0, g_1, \ldots, g_m\) of \(G(x)\).

outputFormat

Output a single line containing \(2^n\) integers. The \(i\)-th integer (0-indexed) should be the value of \([x^S]\,G(F(x))\) modulo 998244353, where \(S\) is the subset corresponding to the bitmask \(i\).

sample

1 1
1 2
3 4

7 8