给定一个长度为 $n$ 的序列 $a$，你需要支持以下四种操作：

1. $1\ x\ k$：给 $x$ 倍数的下标位置上的值加 $k$。
2. $2\ x\ k$：给 $x$ 因数的下标位置上的值加 $k$。
3. $3\ x$：查询 $x$ 倍数的下标位置上所有数的和。
4. $4\ x$：查询 $x$ 因数的下标位置上所有数的和。

共有 $m$ 次操作，你需要在每次查询操作后输出答案。

输入格式

第一行输入两个整数 $n,m$（$1\leq n,m\leq 5\cdot 10^5$），表示序列的长度和操作次数。

第二行输入 $n$ 个整数，表示序列 $a_1,\ldots,a_n$（$0\leq a_i\leq 10^9$）。

接下来 $m$ 行，每行输入三个整数 $op\ x\ k$ 或两个整数 $op\ x$（$1\leq op\leq 4,\ 1\leq x\leq n,\ 0\leq k\leq 10^7$），表示一次修改或查询操作。

输出格式

对于每次查询操作，输出一行一个整数，表示答案。

样例

输入

10 7
1 1 4 5 1 4 1 9 1 9
4 8
2 9 3
1 3 2
3 1
3 2
2 8 2
4 10

输出

16
51
30
19