Problem Description

You are performing a show in a circus.

There is a number, initially $x_0$. You perform $K$ operations, where in the $i$-th operation, a number $x$ is uniformly randomly chosen from $[0, 2^n)$. With probability $p$, $x_i$ is $x_{i - 1} \operatorname{or} x$, and with probability $1 - p$, $x_i$ is $x_{i - 1} \operatorname{and} x$.

The value of a scheme is $\sum_{i=1}^k c_{x_{i}}$. For each $i \in [0, 2^n)$, calculate the sum of the values multiplied by the probabilities for all schemes where $x_K = i$, modulo $998244353$.

Input Format

The first line contains four integers $n, p', K, x_0$. $p'$ is the value of $p$ modulo $998244353$.

The second line contains $2^n$ integers, where the $i$-th integer represents $c_{i - 1}$.

Output Format

Output one line with $2^n$ integers separated by spaces, where the $i$-th integer represents the sum of the values multiplied by the probabilities for all schemes where $x_K = i - 1$, modulo $998244353$.

Sample Input and Output

Input Sample #1

2 499122177 2 1
1 1 1 1

Output Sample #1

374341633 374341633 873463809 374341633

Input Sample #2

2 332748118 10 0
1 2 4 8

Output Sample #2

178690412 406663623 594339846 223292982

Notes

For 20% of the data, $K ≤ 20$.

For 40% of the data, $K ≤ 10^3$.

For another 10% of the data, $n = 1$.

For another 10% of the data, $n ≤ 8$.

For another 10% of the data, $p' = 499122177$.

For another 10% of the data, $c_i = 1$.

For 100% of the data, $0 ≤ n ≤ 17$, $1 ≤ K ≤ 10^9$, $0 ≤ x_0 < 2^n$, $0 ≤ p', c_i < 998244353$.

见题面 Input 部分

见题面 Output 部分