配点:300 点
問題文
長さ N の非負整数列 A=(A1,A2,...,AN) があります.
はじめ,A1=A2=⋯=AN=1 です.
この数列 A に対して,Q 回の操作を行ってください.
k(1≤k≤Q) 回目の操作は以下です:
- lk≤i≤rk を満たす任意の整数 i について,Ai を Ai×xk で置換する.
その後,1≤i≤N を満たす任意の整数 i について,以下のように定められる整数値 Di を求めてください:
- Di:=(Ai の正の約数の個数)mod998244353 .
制約
- 1≤Φ≤104
- 1≤N,Q
- ∑ϕΦϕ(N),∑ϕΦϕ(Q)≤105
- 1≤li≤ri≤N(1≤i≤Q)
- 1≤xi≤100(1≤i≤Q)
- 入力はすべて整数
入力
各テストケースの入力は,それぞれ以下の形式で与えられる:
出力
N 個の整数 D1,D2,…,DN を空白区切りで一行に出力せよ.
サンプル
入力例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
5 回目までの操作後,A=(3,1,4,1,5) を満たします.
6 回目までの操作後,A=(6,2,8,1,5) を満たします.
7 回目までの操作後,A=(6,6,24,3,5) を満たします.
8 回目までの操作後,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
入力例3
2
4 2
1 2 2
2 3 3
3 3
2 3 3
1 2 1
1 3 1