题目描述

片场摆了那么多伞，能给大祥老师一把吗/kel

给定 $n,m$ ，现在有 $n$ 把伞，第 $i$ 把伞的质量是 $a_i$ 。对于 $k=0,1,2,\dots,n$ ，你需要解决以下问题：

计算有多少集合 $S\subseteq \{1,2,\dots,n\}$ 满足：存在 $T\subseteq S$ 使得 $|T|=|S|-k$ 且

$\sum\limits_{x\in T}a_x\geq m$ 。

答案对 $998244353$ 取模。

输入格式

第一行两个整数 $n,m$ 。含义如题所示。

第二行包含 $n$ 个整数，第 $i$ 个整数表示 $a_i$ 。

输出格式

输出 $n+1$ 行，每行一个整数，第 $i$ 行的整数表示 $k=i-1$ 时的答案。

样例

样例输入

4 7
3 1 5 2

样例输出

6
4
1
0
0

数据范围

对于所有数据，$1\le n,m\le 3*10^3,1\le a_i\le 3*10^3$ 。

子任务 1 ( 20% ) : $1\le n,m\le 10$ 。

子任务 2 ( 20% ) : $1\le n,m\le 100$ 。

子任务 3 ( 20% ) : $1\le n,m\le 300$ 。

子任务 4 ( 40% ) : 无特殊限制。