Problem Statement

There are $N$ types of jewels numbered from $1$ to $N$. You have an infinite number of jewels of all types. Jewels of the same type are indistinguishable. Also, there is an integer $U$ that is $2$ or greater. The beauty of each jewel is represented by an integer value between $2$ and $U$, inclusive, and the beauty of jewel $i$ is $b_i$.

For each integer $x$ satisfying $2 \leq x \leq U$, let $f(x)$ be the answer to the following problem:

You will arrange some jewels in a circular pattern to make a necklace. Find the number, modulo $998244353$, of necklaces such that the product of the beauties of the jewels used equals $x$. Here, two necklaces are considered the same and counted only once if they match after rotation. However, two necklaces are counted separately if they do not match just by rotation, even if they match after flipping upside down and rotating. For example, consider the following:

• Necklace A: A necklace formed by arranging jewels $1$, $2$, $3$ in this order clockwise.
• Necklace B: A necklace formed by arranging jewels $2$, $3$, $1$ in this order clockwise.
• Necklace C: A necklace formed by arranging jewels $1$, $3$, $2$ in this order clockwise.

Here, necklaces A and B are considered the same and counted only once, but necklaces A and C are counted separately.

Compute $f(2), f(3), \dots, f(U)$.

Constraints

• $1 \leq N \leq 5 \times 10^5$
• $2 \leq U \leq 5 \times 10^5$
• $2 \leq b_i \leq U$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N U
b_1 b_2 \dots b_N

Output

Output $f(2), f(3), \dots, f(U)$ separated by spaces in one line.