问题描述

生日礼物，小猫君从妈妈那里得到了期待已久的自动MOD取機。

这个自动MOD取機是一台能显示变量 $A_{1}～A_{N}$ 值的机器，小猫君通过操作这台机器上的命令来玩耍。但是他太过兴奋使用过度，导致自动MOD取機开始出现奇怪的行为。

原本的自动MOD取機有以下命令：

设定

执行该命令后，将 $A_1～A_N$ 的值设为0。

命令1

输入 $p,v$ 的值。当执行该命令后的第 $i$ 次命令时，在 $A_1～A_p$ 中，将所有满足 $i+v$ 除以 $i$ 的余数大于等于 $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$。

分值

本问题没有部分分。

输出

对于每次命令2，按顺序输出结果。

输入示例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