设 $$$c$$$ 为某个正整数。我们称正整数数组 $$$a_1, a_2, \ldots, a_n$$$ 为 $$$c$$$ 数组,如果对于所有 $$$i$$$ 条件 $$$1 \leq a_i \leq c$$$ 都满足。我们称 $$$c$$$-array $$$b_1, b_2, \ldots, b_k$$$ 为 $$$c$$$-array $$$a_1, a_2, \ldots, a_n$$$ 的子数组,如果存在这样一组 $$$k$$$ 索引 $$$1 \leq i_1 < i_2 < \ldots < i_k \leq n$$$ $$$b_j = a_{i_j}$$$ 对于所有 $$$1 \leq j \leq k$$$。让我们将 $$$c$$$ 数组 $$$a_1, a_2, \ldots, a_n$$$ 的密度定义为最大非负整数 $$$p$$$,这样任何包含 $$$p$$$ 数字的 $$$c$$$ 数组都是 $$$a_1, a_2, \ldots, a_n$$$ 的子数组。
给你一个数字 $$$c$$$ 和一些 $$$c$$$ 数组 $$$a_1, a_2, \ldots, a_n$$$。对于所有 $$$0 \leq p \leq n$$$,找到索引序列的数量 $$$1 \leq i_1 < i_2 < \ldots < i_k \leq n$$$ 对于所有 $$$1 \leq k \leq n$$$,使得数组 $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ 的密度等于$$$p$$$。通过模 $$$998\,244\,353$$$ 找到这些数字,因为它们可能太大。
输入
第一行包含两个整数 $$$n$$$ 和 $$$c$$$,用空格分隔 ($$$1 \leq n, c \leq 3\,000$$$)。第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$,用空格分隔 ($$$1 \leq a_i \leq c$$$)。
输出
打印 $$$n + 1$$$ 数字 $$$s_0, s_1, \ldots, s_n$$$。对于所有 $$$1 \leq k \leq n$$$,$$$s_p$$$ 应等于索引序列 $$$1 \leq i_1 < i_2 < \ldots < i_k \leq n$$$ 模 $$$998\,244\,353$$$,这样数组的密度 $$$a_{i_1}, a_{i_2}, \ldots,a_{i_k}$$$ 等于$$$p$$$。
示例
输入 #1
4 1 1 1 1 1
输出 #1
0 4 6 4 1
输入 #2
3 3 1 2 3
输出 #2
6 1 0 0
输入 #3
5 2 1 2 1 2 1
输出 #3
10 17 4 0 0 0
注意
在第一个示例中,很容易看出数组的密度始终等于其长度。存在具有一个索引的 $$$4$$$ 序列,具有两个索引的 $$$6$$$,具有三个索引的 $$$4$$$ 和具有四个索引的 $$$1$$$。
在第二个示例中,使数组具有非零密度的唯一索引序列是所有索引,因为在其他情况下,数组中不会有至少一个从 $$$1$$$ 到 $$$3$$$ 的数字,因此它不会满足 $$$p \geq 1$$$ 的密度条件。