Peculiar Partitioning II

You are given an array $a$ of length $n$. Each element of the array is a non-negative integer less than $2^k$. You have to partition it into two non-empty sub-sequences $X$ and $Y$ such that each element belongs to exactly one of $X$ or $Y$. The score of such a partitioning is given by $(x_1 \wedge x_2 \cdots \wedge x_{|X|}) \vee (y_1 \wedge y_2 \cdots\wedge y_{|Y|})$. Here, $\wedge$ denotes the bitwise AND operation and $\vee$ denotes the bitwise OR operation.

For each $x$ between $0$ and $2^k-1$, find the number of ways to partition the array such that the score is $x$. Since this number can be large, you only need to find it modulo $998244353$.

Two ways of partitioning are considered different if and only if there exists a pair of indices $i, j$ such that they are in the same part in one way, but in different parts in the other.

Input

The first line contains two space separated integers, $n$ and $k$.

The second line contains $n$ space-separated integers $a_1,a_2,\cdots ,a_n.$

Constraints

• $2 \leq n \leq 3 \times 10^5$

• $1\leq k \leq 18$

• $0 \leq a_i <2^k$

Output

Output $2^k$space separated integers $f_0, f_1, \cdots, f_{2^k-1}$. where, $f_x$ is the number of ways, modulo $998244353$, to partition such that the score is $x$.

Samples

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

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

Input	Output
2 1 0 1	0 1