Problem Description

You are given an integer $K$, and two arrays $a_1, a_2, \ldots, a_{2^K - 1}$ and $b_1, b_2, \ldots, b_{2^K - 1}$, each of length $2^K - 1$.

There is an undirected complete graph $G$ with $2^K$ vertices, labeled from $0$ to $2^K - 1$.

For a spanning tree $T$ of graph $G$, define

$$\begin{aligned} A(T) &= \prod_{(u,v)\in T} a_{u\oplus v},\\ B(T) &= \sum_{(u,v)\in T} b_{u\oplus v},\\ C(T) &= \bigoplus_{(u,v)\in T} (u\oplus v). \end{aligned}$$

For each $0 \le x < 2^K$, you need to compute

$$\left(\sum_{\substack{T\\ C(T)=x}} A(T)B(T)^p\right) \bmod 998244353,$$

where $p$ is a given constant.

It is defined that $0^0=1$.

An undirected complete graph means there is an undirected edge between every pair of distinct vertices. A spanning tree means choosing some edges so that all vertices are connected and there is no cycle. The symbol $\oplus$ denotes bitwise XOR.

Input Format

The first line contains two integers $K, p$ ($1 \le K \le 16$, $0 \le p \le 5$).

The next line contains $2^K - 1$ integers; the $i$-th integer denotes $a_i$ ($0 \le a_i < 998244353$).

The next line contains $2^K - 1$ integers; the $i$-th integer denotes $b_i$ ($0 \le b_i < 998244353$).

Output Format

Output one line containing $2^K$ integers; the $i$-th integer is the answer for $x = i - 1$.

2 0
1 1 1
1 2 3

4 4 4 4

2 2
2 3 5
1 4 2

5880 5416 10464 9640

Hint

Translated by ChatGPT 5