問題文
作为生日礼物,Snuke 从母亲那里收到了期待已久的自动 MOD 清除机。
这款自动MOD去除机是 N 变量 这是一台显示 A_{1}~A_{N} 值的机器,Snuke正在这台机器上玩弄命令,但他太兴奋并且使用了太多,所以自动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。 |
Snuke别无选择,只能编写一个程序来响应这个命令。 但是,我无法让它工作,所以请帮助我。
然而,Snuke第一次设置后,他并不执行设置命令,只给出第一个设置命令作为输入。
入力
输入将以以下形式从标准输入给出。
N Q (1個目のコマンド) (2個目のコマンド) . . . (Q個目のコマンド)
- 第一行数组数量 N(1≦N≦100,000) Tosunuke执行设置命令后要执行的命令数 Q(1≦Q≦100,000) 被给予。
- 继续 Q 行中 i(1≦i≦Q) Snuke执行set命令后的行
给出 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 第二个命令的输出是 在线 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