跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F2008. The Child and Binary Tree

  • ID: 2014
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:挑战
  • 上传者:
  • 组合数学
  • 分治
  • FFT
  • 数论
  • 数学
  • 算法思想
  • 挑战
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

The Child and Binary Tree

题目描述

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).

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:


题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 1595 题。保留原作者与原赛事署名。