该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

所有的苦难与背负尽头，
都是行云流水般的此世光阴。
一生所渴求的，全都伤人至深。
而一生所憎恶的，全都令人魂牵梦萦。

Marser 沉迷 $\text{hash}$ 无法自拔，然而他发现自己记不住 $\text{hash}$ 键值了……

Marser 使用的 $\text{hash}$ 函数是一个单纯的取模运算，每一个数 $i$ 被对应到 $i\ \text{mod}\ p$。他现在有一个数列 $a_1, a_2, \dots, a_n$，他采用这种方法，把每一个数 $a_i$ 对应到一个键值 $i\ \text{mod}\ p$。他想知道对于给定的模数 $p$ 和键值 $r$，所有对应到该键值的数的和为多少。同时，Marser 可能会发现他的数列出了一些问题，所以他还想随时更改数列中任意一项的值。

现在 Marser 有 $q$ 个请求，每个请求可能是修改或是询问。对于每一个询问，你需要给出正确的答案。如果你不能在 $1\text{s}$ 内正确回答所有询问，Marser 就会让 hotwords 把你给续了。

Input Format

从文件 hash.in 读入。

第一行两个整数 $n$，$q$，表示数列长度和请求数量。
第二行 $n$ 个整数，表示初始的序列。
接下来 $q$ 行，每行三个整数 $opt$，$x$，$y$；

若 $opt=1$，则询问在 $\text{mod}\ x$ 时，所有对应到键值 $y$ 的数的和。
若 $opt=2$，则将数列第 $x$ 项修改为 $y$。

Output Format

输出到文件 hash.out 中。

对于每个询问，输出相应的答案。

Sample

样例输入 1

10 5
1 2 3 4 5 6 7 8 9 10
1 2 1
2 1 20
1 3 1
2 5 1
1 5 0

样例输出 1

25
41
11

样例 2

见下发文件中的 hash2.in 及 hash2.ans。

该样例满足子任务二的性质。

样例 3

见下发文件中的 hash3.in 及 hash3.ans。

该样例满足子任务三的性质。

Hint

本题采用子任务制，子任务分值如下：

** Subtask #1 (30 points) : $n, q \le 1000$**
** Subtask #2 (20 points) : 对于所有 $n, q > 1000$ 的测试点，所有询问中的模数都相等。**
** Subtask #3 (50 points) : 无特殊限制。**

对于 $100\%$ 的数据，保证 $n, q \le 10^5$，输出的所有数据在 int 范围内。