You are performing in a circus.
There is a number, initially $x_0$. Perform $K$ operations. In the $i$-th operation, a number $x$ is chosen uniformly at random from $[0, 2^n)$. $x_i$ is $x_{i-1} \text{ or } x$ with probability $p$, and $x_i$ is $x_{i-1} \text{ and } x$ with probability $1-p$.
The weight of a sequence of operations is $\sum_{i=1}^K c_{x_i}$. For each $i \in [0, 2^n)$, calculate the sum of (weight $\times$ probability) over all scenarios where $x_K = i$, modulo $998244353$.
Input
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
Output a single line containing $2^n$ space-separated integers, where the $i$-th integer represents the sum of (weight $\times$ probability) over all scenarios where $x_K = i-1$, modulo $998244353$.
Constraints
- For 20% of the data, $K \le 20$.
- For 40% of the data, $K \le 10^3$.
- For another 10% of the data, $n = 1$.
- For another 10% of the data, $n \le 8$.
- For another 10% of the data, $p' = 499122177$.
- For another 10% of the data, $c_i = 1$.
- For 100% of the data, $0 \le n \le 17, 1 \le K \le 10^9, 0 \le x_0 < 2^n, 0 \le p', c_i < 998244353$.
Examples
Input 1
2 499122177 2 1 1 1 1 1
Output 1
374341633 374341633 873463809 374341633
Input 2
2 332748118 10 0 1 2 4 8
Output 2
178690412 406663623 594339846 223292982