G - Necklace 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 625 点

問題文

1 から N の番号のついた N 種類の宝石があります。あなたは全ての種類の宝石を無限に持っています。同じ種類の宝石同士は区別できません。
また、2 以上の整数 U があります。各宝石の美しさは 2 以上 U 以下の整数値で表され、宝石 i の美しさは b_i です。

2 \leq x \leq U を満たす整数 x について、以下の問題の答えを f(x) と置きます。

あなたはいくつかの宝石を円形状に並べてネックレスを作ることにしました。
使用した宝石の美しさの総積が x になるようなネックレスの個数を 998244353 で割った余りを求めてください。
ただし、2 つのネックレスは回転させて一致する時は同じネックレスとみなして 1 回だけ数えます。また、2 つのネックレスは上下をひっくり返した上で回転させて一致する場合でも、単に回転させて一致することがなければ別々に数えます。例えば、

  • ネックレス A: 宝石 1, 宝石 2, 宝石 3 をこの順に時計回りに並べてできるネックレス
  • ネックレス B: 宝石 2, 宝石 3, 宝石 1 をこの順に時計回りに並べてできるネックレス
  • ネックレス C: 宝石 1, 宝石 3, 宝石 2 をこの順に時計回りに並べてできるネックレス

とすると、ネックレス A とネックレス B は同じネックレスとみなして 1 回だけ数えますが、ネックレス A とネックレス C は別々に数えます。

f(2), f(3), \dots, f(U) を計算してください。

制約

  • 1 \leq N \leq 5 \times 10^5
  • 2 \leq U \leq 5 \times 10^5
  • 2 \leq b_i \leq U
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N U
b_1 b_2 \dots b_N

出力

f(2), f(3), \dots, f(U) を空白区切りで 1 行に出力せよ。

入力例 1

4 6
2 2 3 4

出力例 1

2 1 4 0 2

例えば x=4 の時、条件を満たすネックレスは次の 4 個です。

  • 宝石 1, 宝石 1 をこの順に時計回りに並べてできるネックレス
  • 宝石 1, 宝石 2 をこの順に時計回りに並べてできるネックレス
  • 宝石 2, 宝石 2 をこの順に時計回りに並べてできるネックレス
  • 宝石 4 を並べてできるネックレス

入力例 2

4 16
2 2 2 2

出力例 2

4 0 10 0 0 0 24 0 0 0 0 0 0 0 70

入力例 3

14 12
10 2 2 3 8 7 11 6 12 4 9 5 3 2

出力例 3

3 2 7 1 7 1 15 4 4 1 24

Score : 625 points

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.

Sample Input 1

4 6
2 2 3 4

Sample Output 1

2 1 4 0 2

For example, when x=4, the following four necklaces satisfy the condition:

  • A necklace formed by arranging jewels 1, 1 in this order clockwise.
  • A necklace formed by arranging jewels 1, 2 in this order clockwise.
  • A necklace formed by arranging jewels 2, 2 in this order clockwise.
  • A necklace formed by arranging jewel 4.

Sample Input 2

4 16
2 2 2 2

Sample Output 2

4 0 10 0 0 0 24 0 0 0 0 0 0 0 70

Sample Input 3

14 12
10 2 2 3 8 7 11 6 12 4 9 5 3 2

Sample Output 3

3 2 7 1 7 1 15 4 4 1 24