给定一个整数 $K$ 和两个大小均为 $2^K - 1$ 的数组 $a_{1 \sim 2^K-1}$ 和 $b_{1 \sim 2^K-1}$。

有一个大小为 $2^K$ 的无向完全图 $G$，其顶点编号为 $0 \sim 2^K - 1$。

对于 $G$ 的一棵生成树 $T$，定义 $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)$。

对于每个 $0 \le x < 2^K$，计算 $\left( \sum_{T, C(T) = x} A(T) B(T)^p \right) \bmod 998244353$，其中 $p$ 是给定的常数。

我们定义 $0^0 = 1$。

输入格式

第一行包含两个整数 $K, p$ ($1 \le K \le 16$，$0 \le p \le 5$)。

第二行包含 $2^K - 1$ 个整数，其中第 $i$ 个整数为 $a_i$ ($0 \le a_i < 998244353$)。

第三行包含 $2^K - 1$ 个整数，其中第 $i$ 个整数为 $b_i$ ($0 \le b_i < 998244353$)。

输出格式

输出单行，包含 $2^K$ 个整数，其中第 $i$ 个整数是 $x = i - 1$ 时的答案。

样例

输入样例 1

2 0
1 1 1
1 2 3

输出样例 1

4 4 4 4

输入样例 2

2 2
2 3 5
1 4 2

输出样例 2

5880 5416 10464 9640