题目描述

You work at the Identifiability in Container Packing Center, where you research the uniqueness of container packings.

You are given $N$ items. Item $i$ has a positive integer weight $A_i$ ($1 \leq i \leq N$).

You consider packing a (nonempty) subset $S \subseteq \{1, 2, \ldots, N\}$ of the items into containers. You may use any number of nonempty containers (empty containers are not allowed). Fix a positive integer $w$ denoting the capacity of each container. A valid packing of $S$ is an assignment of the items in $S$ to containers that satisfies all of the following:

• Cover: Every item in $S$ is placed in exactly one container.
• Capacity: In each container, the total weight of its items is at most $w$.
• Non-mergeability: For any two distinct containers $A$ and $B$, the total weights of the items contained in $A$ or $B$ is strictly greater than $w$ (i.e., no two containers can be merged into a single container without violating capacity $w$).

Containers are indistinguishable and items are distinct even if some have the same weight. Two packings are considered the same if and only if they induce the same partition of $S$; equivalently, for any distinct $i, j \in S$, items $i$ and $j$ are in the same box in one packing if and only if they are in the same box in the other.

For a fixed $w$, call a subset $S$ uniquely packable if there is exactly one valid packing of $S$ that satisfies all conditions.

You are given an integer $W$. Let $f(w)$ ($w = 1, 2, \ldots, W$) be the number of uniquely packable nonempty subsets for capacity $w$. For each $w = 1, 2, \ldots, W$, output $f(w)$ modulo $998244353$. In other words, for each $w = 1, 2, \ldots, W$, define

$$f(w) = \#\{S \subseteq \{1, 2, \ldots, N\} \mid S \text{ is nonempty and uniquely packable for capacity } w\}. $$

Output $W$ integers; for each $w = 1, 2, \ldots, W$, print $f(w)$ modulo $998244353$.

输入格式

The input consists of a single test case of the following format.

$$\begin{aligned} & N \ W \\ & A_1 \ A_2 \ \cdots \ A_N \end{aligned} $$

The first line contains two integers $N$ ($1 \leq N \leq 5000$) representing the number of items and $W$ ($1 \leq W \leq 5000$) representing upper bound on the capacity parameter $w$ (i.e., the maximum capacity to consider). The second line contains $N$ positive integers $A_1, A_2, \ldots, A_N$ ($1 \leq A_i \leq W$). Each $A_i$ represents the weight of the item $i$.

输出格式

Output $W$ integers in a single line separated by spaces: for each $w = 1, 2, \ldots, W$, the $w$-th integer is $f(w)$ modulo $998244353$ (the answer for capacity $w$).

4 4
1 3 2 4

1 3 7 13

3 9
9 1 4

1 1 1 3 3 3 3 3 7

2 2
2 2

0 3