F. The Game Club
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Disclaimer: This story is just a "What if", discretion is advised.

The members of the "2880 Algorithm Club" are tired of participating in so many contests and no longer want to do competitive programming :( They have been training for years and have not achieved their goals. The promises made by the team members of "Que Empató" have not been fulfilled, everyone has already reached blue or purple, but it has not been enough to beat the other teams and they do not understand the reason for so many defeats. But the truth is that the proud members of the club did not listen to their mentors, they were carried away by their individuality and never dared to train in what really makes us great, teamwork.

That is why the members of the "2880 Algorithm Club" decided to close the club and open a new club, "The Game Club", dishonoring one of their mentors by removing the sacred number from the name. The game club meets every Thursday at the Cowork Café and they play bets, they sit at a round table and each member of the club chooses their favorite number (the number 2880 is prohibited from being chosen), then they proceed to roll a die with $$$m$$$ faces with integers from $$$1$$$ to $$$m$$$, where each number has the same probability of coming out. The players sit in a certain order and each one rolls the die clockwise, the game ends if the player rolling the die gets a divisor of their favorite number and they win the game, it is worth mentioning that the table is round, so the game can go around the table several times.

Calculate for each member the probability of winning.

Input

The first line contains two integers $$$n$$$, $$$m$$$ $$$(2\le n \le 10^5 ; 1\le m \le 10^{13})-$$$ where $$$n$$$ is the number of club members and $$$m$$$ is the number of faces on the die.

The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n(1 \le a_i \le m; a_i \neq 2880)-$$$ the favorite numbers of each member in the order they are seated.

Output

Print the answer to the problem, $$$n$$$ integers, where the i-th represents the probability of the i-th member winning.

It can be shown that the probability can be represented as an irreducible fraction $$$\frac{x}{y}$$$.

For each probability, print $$$xy^{-1}$$$ modulo $$$998244353$$$.

Examples
Input
5 1
1 1 1 1 1
Output
1
0
0
0
0
Input
5 2
1 2 1 1 1
Output
499122177
499122177
0
0
0
Input
5 2
1 1 1 1 1
Output
64402862
32201431
515222892
257611446
128805723
Input
1 5
3
Output
1