H - Range Multiplication Query [Divisors ver.]

2 secs 1024 MB
uni_kakurenbo's icon uni_kakurenbo

配点:300300

問題文

長さ NN の非負整数列 A=(A1,A2,...,AN)A = (A_1, A_2, ..., A_N) があります.
はじめ,A1=A2==AN=1A_1 = A_2 = \cdots = A_N = 1 です.

この数列 AA に対して,QQ 回の操作を行ってください.
k  (1kQ)k \; \scriptsize (1 \leq k \leq Q) 回目の操作は以下です:

  • lkirkl_k \leq i \leq r_k を満たす任意の整数 ii について,AiA_iAi×xkA_i \times x_k で置換する.

その後,1iN1 \leq i \leq N を満たす任意の整数 ii について,以下のように定められる整数値 DiD_i を求めてください:

  • Di(AiD_i \coloneqq (A_i の正の約数の個数)mod998244353) \bmod 998244353

制約

  • 1Φ1041 \leq \Phi \leq 10^4
  • 1N,Q1 \leq N, Q
  • ϕΦϕ(N),ϕΦϕ(Q)105\sum_{\phi} \Phi_{\phi}(N), \sum_{\phi} \Phi_{\phi}(Q) \leq 10^5
  • 1liriN  (1iQ)1 \leq l_i \leq r_i \leq N \; \scriptsize (1 \leq i \leq Q)
  • 1xi100  (1iQ)1 \leq x_i \leq 100 \; \scriptsize (1 \leq i \leq Q)
  • 入力はすべて整数

入力

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

NQN \enspace Q
l1r1x1l_1 \enspace r_1 \enspace x_1
l2r2x2l_2 \enspace r_2 \enspace x_2
\vdots
lQrQxQl_Q \enspace r_Q \enspace x_Q

出力

NN 個の整数 D1,D2,,DND_1, D_2, \ldots, D_N を空白区切りで一行に出力せよ.

サンプル

入力例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

55 回目までの操作後,A=(3,1,4,1,5)A = (3, 1, 4, 1, 5) を満たします.
66 回目までの操作後,A=(6,2,8,1,5)A = (6, 2, 8, 1, 5) を満たします.
77 回目までの操作後,A=(6,6,24,3,5)A = (6, 6, 24, 3, 5) を満たします.
88 回目までの操作後,A=(6,6,96,12,5)A = (6, 6, 96, 12, 5) を満たします.


入力例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

Submit


Go (1.21)