Codeforces Round 250 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

divide and conquer

fft

number theory

*3100

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. The Child and Binary Tree

time limit per test

7 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOur child likes computer science very much, especially he likes binary trees.

Consider the sequence of *n* distinct positive integers: *c*_{1}, *c*_{2}, ..., *c*_{n}. 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 {*c*_{1}, *c*_{2}, ..., *c*_{n}}. 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 × 2^{23} + 1, a prime number).

Input

The first line contains two integers *n*, *m* (1 ≤ *n* ≤ 10^{5}; 1 ≤ *m* ≤ 10^{5}). The second line contains *n* space-separated pairwise distinct integers *c*_{1}, *c*_{2}, ..., *c*_{n}. (1 ≤ *c*_{i} ≤ 10^{5}).

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 × 2^{23} + 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:

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/09/2023 02:38:30 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|