给定 $n$ 个物品，定义第 $i$ 个物品的 特征值 为 $a_i$，其中 $a_i$ 是整数且满足 $0\leq a_i < 2^m$ 。

你需要选择若干物品形成一个组合。一个组合的 独特值 为其包含的物品的特征值的 异或和 。

注意，你可以一个物品也不选，此时我们认为独特值为 $0$ 。

当你选择出一个组合后，你会邀请你的两个伙伴来挑选这些物品。

只不过，两个人只约定了一共选出 $B$ 个物品，而忘记保证它们互不冲突，也就是说一个物品可能同时被两人选择。

请注意，一共选出 $B$ 个物品指的是选择次数为 $B$，而不是被选择的物品数为 $B$ 。

你对一个组合产生的 期待值 为两个伙伴从组合中挑选物品的本质不同方案数。

两个方案本质不同当且仅当存在一个物品，使得其在第一个方案中被某个人选择了，而在第二个方案中没有被那个人选择。

对于每个 $0\leq i < 2^m$，你需要对所有独特值为 $i$ 的组合，求出它们的期待值之和。

由于答案可能过大，你只需要输出答案对 $998244353$ 取模的结果。

输入格式

第一行三个整数 $n,m,B$，意义参考题面。\ 接下来一行 $n$ 个整数，第 $i$ 个即 $a_i$，意义参考题面。

输出格式

一行 $2^m$ 个整数，第 $i$ 个数表示独特值为 $i-1$ 的所有组合的期待值之和，对 $998244353$ 取模后的结果。

样例输入 1

3 3 2
1 2 5

样例输出 1

0 1 1 6 6 1 15 6

样例解释 1

独特值为 $3$ 的仅有一种组合，即选择特征值为 $1$ 和特征值为 $2$ 的物品。\ 此时可能的挑选方案有（我们记两个人分别为 A, B）：

• A 选择两个。
• B 选择两个。
• A 选择第一个，B 同样选择第一个。
• A 选择第二个，B 同样选择第二个。
• A 选择第一个，B 选择第二个。
• A 选择第二个，B 选择第一个。

一共六种方案，因此该组合期待值为 $6$ 。

样例输入 2 / 样例输出 2

见下发文件 ex_goods2.in / ex_goods2.ans 。

该样例约束与测试点 $3\sim 5$ 一致。

样例输入 3 / 样例输出 3

见下发文件 ex_goods3.in / ex_goods3.ans 。

该样例约束与测试点 $14\sim 17$ 一致。

样例输入 4 / 样例输出 4

见下发文件 ex_goods4.in / ex_goods4.ans 。

该样例约束与测试点 $18\sim 25$ 一致。

数据范围

本题共 $25$ 个测试点，每个测试点等分（即每个测试点 $4$ 分）。

对于所有数据，满足：$1\leq n\leq 10^6,1\leq m\leq 20,0\leq B\leq n$ 。