← 返回题目列表

Codeforces · 438/E

E. 子树和二叉树

中文机器翻译题面 查看原题

我们的孩子非常喜欢计算机科学,尤其喜欢二叉树。

考虑 n 个不同正整数的序列:c1, c2, ..., cn。当且仅当对于每个顶点 v,v 的权重位于集合 {c1, c2, ..., cn} 中时,孩子才称顶点加权有根二叉树为好树。我们的孩子还认为顶点加权树的权重是所有顶点权重的总和。

给定一个整数 m,你能对所有 s (1 ≤ s ≤ m) 计算出权重为 s 的良好顶点加权有根二叉树的数量吗?请检查示例,以便更好地了解哪些树木被认为是不同的。

我们只想知道对 998244353(7 × 17 × 223 + 1,质数)求模的答案。

输入

第一行包含两个整数 n, m (1 ≤ n ≤ 105; 1 ≤ m ≤ 105)。第二行包含 n 个空格分隔的成对不同整数 c1, c2, ..., cn。 (1≤ci≤105)。

输出

打印 m 行,每行包含一个整数。第 i 行必须包含权重恰好等于 i 的良好顶点加权有根二叉树的数量。打印以 998244353 为模的答案(7 × 17 × 223 + 1,质数)。

示例

输入 #1

2 3
1 2

输出 #1

1
3
9

输入 #2

3 10
9 4 3

输出 #2

0
0
1
1
0
2
4
2
6
15

输入 #3

5 10
13 10 6 4 15

输出 #3

0
0
0
1
0
1
0
2
0
5

注意

在第一个示例中,有 9 个良好的顶点加权有根二叉树,其权重恰好等于 3: