K. Random XOR
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ and two integers $$$m$$$ and $$$k$$$. For each position $$$i$$$, independently choose an integer $$$d_i$$$ ($$$0\le d_i\le k$$$) and replace its value with $$$a_i+d_i$$$.

For every $$$0\le s \lt 2^m$$$, count the choices satisfying

$$$$$$(a_1+d_1)\oplus\cdots\oplus(a_n+d_n)=s$$$$$$.

Here, $$$\oplus$$$ denotes the bitwise XOR operation. Write the two nonnegative integers in binary and pad them with leading zeros to the same length. For each position, the resulting bit is $$$1$$$ if the two corresponding bits differ, and $$$0$$$ if they are equal. For example, $$$(0011)_2\oplus(0101)_2=(0110)_2$$$.

Two choices are different if and only if the chosen increments differ at at least one position. Print all answers modulo $$$998~244~353$$$.

Input

There is only one test case in each test file.

The first line contains three integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$1\le n\le500000$$$, $$$1\le m\le19$$$, $$$0\le k\le100$$$). It is guaranteed that $$$2^m-k \gt 0$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i \lt 2^m-k$$$).

Output

Print $$$2^m$$$ integers. The $$$j$$$-th integer is the number of choices for $$$s=j-1$$$, modulo $$$998~244~353$$$.

Examples
Input
2 2 1
0 1
Output
1 1 1 1
Input
3 3 2
0 1 3
Output
3 2 2 2 4 4 5 5
Note

In the first example, the first number can become $$$0$$$ or $$$1$$$, and the second can become $$$1$$$ or $$$2$$$. The four choices give XOR values $$$1,2,0,3$$$, so all answers are $$$1$$$.