H - Range Multiplication Query [Divisors ver.]

2 secs 1024 MB
uni_kakurenbo

配点:

問題文


長さ の非負整数列 があります.
はじめ, です.

この数列 に対して, 回の操作を行ってください.
回目の操作は以下です:

  • を満たす任意の整数 について, で置換する.

その後, を満たす任意の整数 について,以下のように定められる整数値 を求めてください:

  • の正の約数の個数

制約


  • 入力はすべて整数

入力


各テストケースの入力は,それぞれ以下の形式で与えられる:





出力


個の整数 を空白区切りで一行に出力せよ.

サンプル


入力例1
1
5 8
1 1 3
2 2 1
3 3 4
4 4 1
5 5 5
1 3 2
2 4 3
3 4 4
出力例1
4 4 12 6 2

回目までの操作後, を満たします.
回目までの操作後, を満たします.
回目までの操作後, を満たします.
回目までの操作後, を満たします.


入力例2
1
4 8
1 1 42
2 2 32
3 3 23
4 4 49
1 3 88
2 4 77
1 4 23
1 2 41
出力例2
160 216 72 16

入力例3
2
4 2
1 2 2
2 3 3
3 3
2 3 3
1 2 1
1 3 1
出力例3
2 4 2 1
1 2 2

提出


Go (1.14)