Range Multiplication Sum

長さ の整数列 が与えられます。 個のクエリを順に処理してください。
番目のクエリでは、まず整数 が与えられます。ここで、 は か のどちらかです。
次に、 の値に応じてクエリの内容を表す入力が与えられるので、以下のように処理してください。

• のとき
  整数 が与えられるので、 を に変更してください。
• のとき
  整数 が与えられるので、 を で割った余りを出力してください。

• または
• 入力は全て整数 　　

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

行目から 行目の は以下のいずれかです。

の各クエリについて、改行区切りで答えを出力してください。

6 4
4 1 8 2 6 9
2 2 4
2 4 6
1 6 0
2 4 6

26
84
12

番目のクエリは を出力せよというものです。 なので、 と出力します。

番目のクエリは を出力せよというものです。 なので、 と出力します。

番目のクエリは を に変更せよというものです。 となります。

番目のクエリは を出力せよというものです。 なので、 と出力します。

2 1
998244352 998244352
2 1 2

1

ですが、 で割った余りを出力する必要があることに注意してください。