给定一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \dots, A_N)$。对于 $k = 0, 1, \dots, N$，求解以下问题。

求满足以下条件的 $\{1, 2, \dots, N\}$ 的子集 $S$ 的数量，结果对 $998244353$ 取模。

• 存在一个 $S$ 的子集 $T$，使得 $|T| = |S| - k$ 且 $\sum_{i \in T} A_i \ge M$。

数据范围

• $1 \le N \le 3000$
• $1 \le M \le 3000$
• $1 \le A_i \le 3000$

输入格式

输入通过标准输入按以下格式给出：

$N \ M$ $A_1 \ A_2 \dots A_N$

输出格式

输出 $N + 1$ 行。第 $i$ 行（$1 \le i \le N + 1$）输出 $k = i - 1$ 时的答案。

样例

输入 1

4 7
3 1 5 2

输出 1

6
4
1
0
0

输入 2

1 5
7

输出 2

1
0

输入 3

9 18
1 9 5 6 2 7 1 4 8

输出 3

346
309
230
126
46
10
1
0
0
0

说明

对于第一个样例： 以 $k = 1$ 的情况为例进行说明。

• 对于 $S = \{1, 3, 4\}$，如果我们令 $T = \{3, 4\}$，则 $|T| = |S| - 1$ 且 $\sum_{i \in T} A_i \ge 7$，因此它满足条件。

其他满足条件的子集为 $S = \{1, 2, 3\}, \{2, 3, 4\}, \{1, 2, 3, 4\}$，总计 3 个子集。因此，当 $k = 1$ 时，答案为 4。