题目描述

给出一个整数 $K$，以及两个长度为 $2^K - 1$ 的数组 $a_1, a_2, \ldots, a_{2^K - 1}$ 和 $b_1, b_2, \ldots, b_{2^K - 1}$。

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

对于图 $G$ 的一棵生成树 $T$，定义

$$\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}$$

你需要对于每个 $0 \le x < 2^K$，求出

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

其中 $p$ 为一个给定的常数。

规定 $0^0=1$。

无向完全图表示任意两个不同点之间都有一条无向边；生成树表示选出若干条边，使得所有点连通且不存在环；符号 $\oplus$ 表示按位异或。

输入格式

第一行包含两个整数 $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$ 时的答案。

2 0
1 1 1
1 2 3

4 4 4 4

2 2
2 3 5
1 4 2

5880 5416 10464 9640