5615: The Child and Binary Tree
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：1
通过：1
题目描述
E. The Child and Binary Tree
time limit per test
7 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Our child likes computer science very much, especially he likes binary trees.
Consider the sequence of n distinct positive integers: c1,c2,...,cn. The child calls a vertex-weighted rooted binary tree good if and only if for every vertex v, the weight of v is in the set {c1,c2,...,cn}. Also our child thinks that the weight of a vertex-weighted tree is the sum of all vertices' weights.
Given an integer m, can you for all s (1≤s≤m) calculate the number of good vertex-weighted rooted binary trees with weight s? Please, check the samples for better understanding what trees are considered different.
We only want to know the answer modulo 998244353 (7×17×223+1, a prime number).
Consider the sequence of n distinct positive integers: c1,c2,...,cn. The child calls a vertex-weighted rooted binary tree good if and only if for every vertex v, the weight of v is in the set {c1,c2,...,cn}. Also our child thinks that the weight of a vertex-weighted tree is the sum of all vertices' weights.
Given an integer m, can you for all s (1≤s≤m) calculate the number of good vertex-weighted rooted binary trees with weight s? Please, check the samples for better understanding what trees are considered different.
We only want to know the answer modulo 998244353 (7×17×223+1, a prime number).
Input
The first line contains two integers n,m (1≤n≤105;1≤m≤105). The second line contains n space-separated pairwise distinct integers c1,c2,...,cn. (1≤ci≤105).
Output
Print m lines, each line containing a single integer. The i-th line must contain the number of good vertex-weighted rooted binary trees whose weight exactly equal to i. Print the answers modulo 998244353 (7×17×223+1, a prime number).
Examples
Input
2 3 1 2
Output
1 3 9
Input
3 10 9 4 3
Output
0 0 1 1 0 2 4 2 6 15
Input
5 10 13 10 6 4 15
Output
0 0 0 1 0 1 0 2 0 5
Note
In the first example, there are 9 good vertex-weighted rooted binary trees whose weight exactly equal to 3:
输入样例 复制
输出样例 复制