E - 自動MOD取り機 解説 /

実行時間制限: 4 sec / メモリ制限: 256 MB

問題文

誕生日プレゼントにすぬけ君は待望の自動MOD取り機をお母さんからもらいました。

この自動MOD取り機は N 個の変数 A_{1}～A_{N} の値を表示する機械であり、すぬけ君はこの機械にあるコマンドをいじくることで遊んでいましたが、興奮して使いすぎてしまったので自動MOD取り機は変な挙動をし始めてしまいました。

本来の自動MOD取り機は以下のようなコマンドがあります。

セット これを実行すると、A_1～A_N の値を0にする。
コマンド1 p,v の値を入力する。このコマンドがセットしてからi回目のコマンドの時、A_1～A_pの中で、i+vで割った余りがi以上の値のものをすべて、 その数より大きい最小のi+vの倍数に置き換える。
コマンド2 p の値を入力する。このコマンドでは A_p の値を出力する。
コマンド3 v の値を入力する。このコマンドでは A_1～A_n すべてにvを加える。

すぬけ君はしょうがないのでこのコマンドに答えるプログラムを組もうとしました。 しかし、なかなかうまくいかないので、助けてください。

ただし、すぬけ君は最初にセットをした後はセットコマンドは実行せず、入力として与えられるのは最初に行われるセットコマンド以外が与えられる。

入力

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

N Q
（1個目のコマンド）
（2個目のコマンド）
.
.
.
（Q個目のコマンド）
  • 一行目には配列の数 N(1≦N≦100,000) とすぬけ君がセットコマンドを行った後に実行するコマンドの数 Q(1≦Q≦100,000) が与えられる。
  • 続く Q 行の内の i(1≦i≦Q) 行目にはすぬけ君がセットコマンドを実行してから i 回目のコマンドが与えられる。
    これらは以下のいずれかである。
     1 p v
    これは、コマンド1 の入力として、p,v が入力で与えられることを表す。これらは、1≦p≦n,1≦v≦10 を満たす。 
     2 p
    これは、コマンド2 の入力として、p が入力で与えられることを表す。これは、1≦p≦n を満たす。 
     3 v
    これは、コマンド3 の入力として、v が入力で与えられることを表す。これは、1≦v≦100,000 を満たす。

配点

この問題には部分点がない。

出力

i 回目のコマンド2 に対する出力を i 行目に出力せよ。

入力例1

5 7
3 5
2 3
1 3 10
2 3
1 4 10
2 3
2 4

出力例1

5
13
15
15

A_{i} の値は以下のように変更される。
[A_{1},A_{2},A_{3},A_{4},A_{5}] : [0,0,0,0,0]→[5,5,5,5,5]→[13,13,13,5,5]→[15,15,15,15,5]

入力例2

3 6
2 1
3 9
1 3 3
2 1
1 1 1
2 1

出力例2

0
12
12