Fairy tales are only beautiful in their reality, yet they are never continued.

Lingluo has recently been learning about prefix sum algorithms and wrote the following program:

read(n),read(a);
for(int i=0;i<=n;i++)read(f[i]);
for(int t=1;t<=n;t++){
    for(int i=1;i<=n;i++)f[i]=f[i]+a*f[i-1];
    ans[t]=f[t];
}

She discovered that this program times out when $n$ is large. Please write a program to help her calculate $\text{ans}_1, \text{ans}_2, \dots, \text{ans}_n$. Since the answers can be very large, you only need to provide the remainder of each number when divided by $998244353$.

Input

The first line contains two positive integers $n, a$.

The next line contains $n+1$ non-negative integers, representing $f_0, f_1, \dots, f_n$.

Output

Output $n$ non-negative integers, representing $\text{ans}_1, \text{ans}_2, \dots, \text{ans}_n$.

Examples

Input 1

2 1
1 2 0

Output 1

3 7

Input 2

10 10
5 9 7 8 0 6 3 2 4 10 1

Output 2

59 1687 55618 1937320 69557006 549579657 621247830 250099579 483510144 968467040

Constraints

For $100\%$ of the data, it is guaranteed that $2 \leqslant n \leqslant 10^6$, $0 \leqslant f_i < 998244353$, and $1 \leqslant a < 998244353$.

Special Property A: The number of $i$ such that $f_i \neq 0$ is at most $100$.

Special Property B: $a=1$.

Special Property C: For all $i \in [0, n]$, $f_i = 1$.

Special Property D: For all $i \in [0, n]$, $f_i = \binom{i+2}{2} = \frac{(i+2)(i+1)}{2}$.