0357 - 殺菌スプレー (Sterilizing Spray)

時間制限 5 秒 / メモリ制限 512 MB / 得点 100 / Writer root / x 1 / 統計 /

TLE
5sec
MLE
512MB
得点
100

問題

　JOI 氏が働く IOI 製薬会社は，新しい殺菌スプレーを開発するために，日々研究実験に励んでいる．
　IOI 製薬会社では殺菌スプレーに対して強さという値を定めている. 強さ x のスプレーとは，細菌が y 個入ったシャーレに 1 回吹き付けた時に，シャーレ内の細菌の個数が y / x の小数点以下を切り捨てた値になるものである．このたび，新たに強さ K のスプレーが開発された．このスプレーの性能をテストするためにシャーレを N 個使って実験を行うことになった．各シャーレには 1 から N までの番号が付けられている．初め，シャーレ i には Ci 個の細菌が入っている．実験では以下の 3 種類の操作をあわせて Q 回行う．

  • 操作 1 : あるシャーレ a に入っている細菌の個数を b 個にする．
  • 操作 2 : まず，1 ≤ l ≤ r ≤ N となる整数 l, r を選ぶ．その後シャーレ l，シャーレ l + 1，...，シャーレ r - 1，シャーレ r にスプレーを吹き付ける．
  • 操作 3 : まず，1 ≤ l ≤ r ≤ N となる整数 l, r を選ぶ．その後シャーレ l，シャーレ l + 1，...，シャーレ r - 1，シャーレ r に入っている細菌の個数の総和を求め，記録する．

　JOI 氏はスプレーが期待通り機能すると仮定したとき，実験がどのような結果になるかが気になった．そこで JOI 氏は，優秀なプログラマーであるあなたに，実験結果の予測を依頼した．
　実験の中で操作 3 によって記録される値を求めるプログラムを作成せよ．

課題

　殺菌スプレーの強さと，実験で行われた操作の情報が与えられたとき，操作 3 によって記録される値を求めるプログラムを作成せよ．

入力

　標準入力から以下の入力を読み込め．

  • 1 行目には，3 個の整数 N, Q, K が空白を区切りとして書かれている．これは実験で強さが K の殺菌スプレー，N 個のシャーレを使用し，Q 回の操作を行うことを表す．
  • 続く N 行のうちの i 行目 (1 ≤ i ≤ N) には，整数 Ci が書かれている．これは初め，シャーレ i には Ci 個の細菌が入っていたことを表す．
  • 続く Q 行のうちの i 行目 (1 ≤ i ≤ Q) には，3 個の整数 Si, Ti, Ui が空白を区切りとして書かれている．これは i 番目の操作の情報である．
    • Si = 1 のとき, a = Ti, b = Ui として操作 1 を行ったことを表す．
    • Si = 2 のとき, l = Ti, r = Ui として操作 2 を行ったことを表す．
    • Si = 3 のとき, l = Ti, r = Ui として操作 3 を行ったことを表す．

出力

　実験中の操作 3 において記録される値を，操作 3 ごとに 1 行で出力せよ．出力の行数は操作 3 の回数と等しい．

制限

　すべての入力データは以下の条件を満たす.

  • 1 ≤ N ≤ 100 000．
  • 1 ≤ Q ≤ 100 000．
  • 1 ≤ K ≤ 10．
  • 0 ≤ Ci ≤ 1 000 000 000 (1 ≤ i ≤ N)．
  • 1 ≤ Si ≤ 3 (1 ≤ i ≤ Q)．
  • Si = 1 のとき，1 ≤ Ti ≤ N および 0 ≤ Ui ≤ 1 000 000 000 (1 ≤ i ≤ Q)．
  • Si = 2, 3 のとき，1 ≤ Ti ≤ Ui ≤ N (1 ≤ i ≤ Q)．

小課題

小課題 1 [5 点]

  • 1 ≤ N ≤ 3 000 を満たす．
  • 1 ≤ Q ≤ 3 000 を満たす．

小課題 2 [10 点]

  • Ci ≤ 1 (1 ≤ i ≤ N) を満たす．
  • Si = 1 のとき，Ui ≤ 1 (1 ≤ i ≤ Q) を満たす．

小課題 3 [10 点]

  • K = 1 を満たす．

小課題 4 [75 点]

　追加の制限はない．

入出力例

入力例 1

5 10 3
1
2
8
1
3
1 2 5
2 3 5
3 2 5
2 1 4
1 3 2
3 3 5
1 2 4
2 1 2
1 1 4
3 1 5

出力例 1

8
3
8
  • 初め，各シャーレに入っている細菌の個数はシャーレ 1 から順に 1 2 8 1 3 のようになっている．
  • シャーレ 2 の細菌の個数を 5 個に変更する．変更後の各シャーレの中身は 1 5 8 1 3 のようになっている．
  • シャーレ 3, 4, 5 の細菌の個数を 3 で割って小数点以下を切り捨てた整数に変更する．変更後の各シャーレの中身は 1 5 2 0 1 のようになっている．
  • シャーレ 2, 3, 4, 5 に入っている細菌の個数の合計は 8 なので， 8 を出力する．
  • シャーレ 1, 2, 3, 4 の細菌の個数を 3 で割って小数点以下を切り捨てた整数に変更する．変更後の各シャーレの中身は 0 1 0 0 1 のようになっている．
  • シャーレ 3 の細菌の個数を 2 個に変更する．変更後の各シャーレの中身は 0 1 2 0 1 のようになっている．
  • シャーレ 3, 4, 5 に入っている細菌の個数の合計は 3 なので， 3 を出力する．
  • シャーレ 2 の細菌の個数を 4 個に変更する．変更後の各シャーレの中身は 0 4 2 0 1 のようになっている．
  • シャーレ 1, 2 の細菌の個数を 3 で割って小数点以下を切り捨てた整数に変更する．変更後の各シャーレの中身は 0 1 2 0 1 のようになっている．
  • シャーレ 1 の細菌の個数を 4 個に変更する．変更後の各シャーレの中身は 4 1 2 0 1 のようになっている．
  • シャーレ 1, 2, 3, 4, 5 に入っている細菌の個数の合計は 8 なので， 8 を出力する．

入力例 2

15 10 3
25
87
32
89
24
99
57
88
10
57
65
42
66
98
13
3 9 12
1 7 15
3 2 9
2 1 14
3 10 13
1 10 6
2 14 14
1 7 96
3 14 15
3 10 12

出力例 2

174
444
76
23
41