Repeated Discrete Fourier Transform

Given a nonnegative integer sequence of length \(2^n\): \(a_0,a_1,\ldots,a_{2^n-1}\), compute the sequence \(A = \text{DFT}^k(a)\), where the discrete Fourier transform (DFT) is defined as

\[ \text{DFT}(b)_i = \sum_{j=0}^{2^n-1} b_j\,\omega^{ij} \pmod{998244353}, \]

with \[ \omega \equiv 3^\frac{998244352}{2^n} \pmod{998244353}. \]

Note that \(\text{DFT}^k\) means applying the DFT transformation \(k\) times. It can be shown that for a sequence \(a\) of length \(N=2^n\) one has:

• \(\text{DFT}^0(a)_i = a_i\).
• \(\text{DFT}^1(a)_i = \text{DFT}(a)_i\).
• \(\text{DFT}^2(a)_i = N\cdot a_{-i}\) (here the index is taken modulo \(N\)).
• \(\text{DFT}^3(a)_i = N\cdot (\text{DFT}(a))_{-i}\) (equivalently, one may compute the DFT using \(\omega^{-1}\)).
• \(\text{DFT}^4(a)_i = N^2\cdot a_i\).

In general, writing \(k=4m+r\) with \(0\le r<4\), the transformation equals:

• If \(r=0\): \(A_i = N^{2m}\,a_i\).
• If \(r=1\): \(A_i = N^{2m}\,(\text{DFT}(a))_i\).
• If \(r=2\): \(A_i = N^{2m+1}\,a_{-i}\).
• If \(r=3\): \(A_i = N^{2m+1}\,(\text{DFT}(a))_{-i}\), which is equivalent to computing the DFT with \(\omega^{-1}\).

All operations are performed modulo \(998244353\).

inputFormat

The first line contains two integers \(n\) and \(k\). (For example, \(0 \le k \le 10^9\))

The second line contains \(2^n\) nonnegative integers \(a_0,a_1,\ldots,a_{2^n-1}\) separated by spaces.

outputFormat

Output \(2^n\) integers representing the sequence \(A = \text{DFT}^k(a)\). The numbers should be printed in order and separated by spaces.

sample

1 0
5 7

5 7