F. Counting Trees
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given an integer $$$K$$$ and two arrays $$$a_{1\sim 2^{K}-1}$$$ and $$$b_{1\sim 2^{K}-1}$$$, each of size $$$2^{K}-1$$$.

There is an undirected complete graph $$$G$$$ of size $$$2^K$$$ with vertices numbered $$$0\sim 2^K - 1$$$.

For a spanning tree $$$T$$$ of $$$G$$$, define $$$A(T)=\prod_{(u,v)\in T}a_{u\oplus v}$$$, $$$B(T)=\sum_{(u,v)\in T}b_{u\oplus v}$$$, $$$C(T)=\oplus_{(u,v)\in T}(u\oplus v)$$$.

For each $$$0\le x \lt 2^K$$$, compute $$$(\sum_{T,C(T)=x}A(T)B(T)^p) \bmod 998244353$$$, where $$$p$$$ is a given constant.

We define $$$0^0=1$$$.

Input

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, where the $$$i$$$-th integer is $$$a_i$$$ ($$$0\le a_i \lt 998244353$$$).

The next line contains $$$2^K-1$$$ integers, where the $$$i$$$-th integer is $$$b_i$$$ ($$$0\le b_i \lt 998244353$$$).

Output

Output a single line with $$$2^K$$$ integers, where the $$$i$$$-th integer is the answer for $$$x=i-1$$$.

Examples
Input
2 0
1 1 1
1 2 3
Output
4 4 4 4
Input
2 2
2 3 5
1 4 2
Output
5880 5416 10464 9640