G. Grand XOR Counting Problem Challenge
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The annual GXCPC (Grand XOR Counting Problem Challenge) begins! This year, Judge Colin has prepared a super difficult counting problem for the contestants! Can you slay this ultimate counting problem and win the championship?

Colin has a sequence of $$$n$$$ non-negative integers $$$a_1,a_2,\cdots,a_n$$$.

He wants to know, for each integer $$$b\in [0, m)$$$, how many ways there are to choose $$$k$$$ distinct indices $$$1 \leq i_1 \lt i_2 \lt i_3 \lt \ldots i_k \leq n$$$ satisfying $$$a_{i_1} \oplus a_{i_2} \oplus \ldots \oplus a_{i_k}=b$$$, where $$$\oplus$$$ represents the bitwise XOR operation.

You only need to output the answers modulo $$$998244353$$$.

Input

The first line contains three integers $$$n,k,m~(1\le n\le 10^6, 1\le k\le n, 1\le m\le 2^{20})$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n~(0\le a_i \lt m)$$$, representing the integer sequence.

Output

One line with $$$m$$$ integers, where the $$$i$$$-th integer represents the answer modulo $$$998244353$$$ for $$$b=i-1$$$.

Example
Input
4 2 4
0 1 2 3
Output
0 2 2 2