Given $n$ items, the characteristic value of the $i$-th item is defined as $a_i$, where $a_i$ is an integer such that $0 \leq a_i < 2^m$.

You need to select a subset of items to form a combination. The unique value of a combination is the XOR sum of the characteristic values of the items it contains.

Note that you may choose not to select any items, in which case the unique value is considered to be $0$.

After you have chosen a combination, you invite your two partners to pick items from it.

However, the two partners only agreed to pick a total of $B$ items, and they forgot to ensure that their choices do not conflict; that is, an item may be chosen by both people simultaneously.

Note: Picking a total of $B$ items refers to the number of selection actions being $B$, not the number of distinct items chosen being $B$.

The expected value of a combination is the number of essentially distinct ways your two partners can pick items from the combination.

Two schemes are essentially distinct if and only if there exists an item such that it was chosen by a specific person in the first scheme but not by that same person in the second scheme.

For each $0 \leq i < 2^m$, you need to calculate the sum of the expected values for all combinations whose unique value is $i$.

Since the answer may be very large, you only need to output the result modulo $998244353$.

Input

The first line contains three integers $n, m, B$, as described in the problem statement. The next line contains $n$ integers, where the $i$-th integer is $a_i$, as described in the problem statement.

Output

A single line containing $2^m$ integers, where the $i$-th integer represents the sum of the expected values of all combinations with a unique value of $i-1$, modulo $998244353$.

Examples

Input 1

3 3 2
1 2 5

Output 1

0 1 1 6 6 1 15 6

Note 1

There is only one combination with a unique value of $3$, which is selecting the items with characteristic values $1$ and $2$. The possible selection schemes (let the two partners be A and B) are:

• A picks two.
• B picks two.
• A picks the first, B also picks the first.
• A picks the second, B also picks the second.
• A picks the first, B picks the second.
• A picks the second, B picks the first.

There are a total of six schemes, so the expected value of this combination is $6$.

Input 2

See the provided file ex_goods2.in / ex_goods2.ans.

This sample constraint is consistent with test cases $3 \sim 5$.

Input 3

See the provided file ex_goods3.in / ex_goods3.ans.

This sample constraint is consistent with test cases $14 \sim 17$.

Input 4

See the provided file ex_goods4.in / ex_goods4.ans.

This sample constraint is consistent with test cases $18 \sim 25$.

Constraints

There are 25 test cases in total, each worth an equal share of points (4 points per test case).

For all data, it is satisfied that: $1 \leq n \leq 10^6, 1 \leq m \leq 20, 0 \leq B \leq n$.