Circus Operation Game

You are performing a circus act. You are given an initial integer \(x_0\) and will perform \(K\) operations. In the \(i\)-th operation, a number \(x\) is chosen uniformly at random from \([0, 2^n)\). Then with probability \(p\) you update \(x_i = x_{i-1} \lor x\) (bitwise OR) and with probability \(1-p\) you update \(x_i = x_{i-1} \land x\) (bitwise AND).

A scheme’s weight is defined as \(\sum_{i=1}^{K} c_{x_i}\). For each \(i \in [0, 2^n)\), compute the sum of (scheme probability multiplied by its weight) over all schemes that end with \(x_K=i\), and output the result modulo \(998244353\).

All formulas are in \(\LaTeX\) format.

inputFormat

The input consists of two lines.

The first line contains four values: n K p x0, where n is a non-negative integer, \(K\) is the number of operations, \(p\) is a probability (given as a decimal number between 0 and 1), and x0 (\(0 \le x0 < 2^n\)) is the initial number.

The second line contains \(2^n\) integers: c0 c1 ... c(2^n-1), where each c_i is the weight coefficient for state \(i\).

outputFormat

Output one line containing \(2^n\) space-separated integers. The \(i\)-th integer (0-indexed) should be the sum of (scheme probability multiplied by its weight) for all schemes with \(x_K=i\), taken modulo \(998244353\).

sample

2 1 1.0 1
5 -1 3 7

0 499122176 0 499122180