题目描述

给你一个长度为 $n$ 的数组 a，请支持如下 2 个操作：

• 1、C x y：将 a[x] 修改为 y
• 2、A x y：询问模 $x$ 余数为 $y$ 的所有位置的数的和

提示:

• 梁老师说过，$\color{red}{当你枚举的数在分母上时，可能就要用到根号算法}$
• 模 $x$ 余数为 $y$ 的所有位置：也就是说每 $x$ 取一个，$[y, y + x, y + 2 \times x, \cdots y + k \times x]$

输入格式

第一行，两个正整数 $n$, $m$，其中 $n$ 代表数组长度，$m$ 代表 操作次数。

第二行，$n$ 个正整数，代表初始序列。

接下来 $m$ 行，首先是一个字符 $\text{cmd}$，然后是两个整数 $x,y$。

• 若 $\text{cmd}=\text{A}$，则询问模 $x$ 余数为 $y$ 的所有位置的数的和。

• 若 $\text{cmd}=\text{C}$，则将 $a[x]$ 修改为 $y$。

输出格式

对于每个询问输出一个正整数，进行回答。

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

25
41
11

提示

【样例一解释】

• A 2 1 的答案是 1+3+5+7+9=25
• C 1 20 之后的数组为 $[20, 2, 3, 4, 5, 6, 7, 8, 9, 10]$
• A 3 1 的答案是 20+4+7+10=41
• C 5 1 之后的数组为 $[20, 2, 3, 4, 1, 6, 7, 8, 9, 10]$
• A 5 0 的答案是 1+10=11

【数据范围】

对于 $10\%$的数据：$n\leq 1000$，$m\leq 1000$。

对于 $60\%$ 的数据：$n\leq 100000$，$m\leq 100000$。

对于 $100\%$ 的数据：$n\leq 150000$，$m\leq 150000$

保证所有数据合法，且 $1\leq a[i] \leq 1000$。

对于询问操作：$1 \le x < n, 0 \le y < x$

对于修改操作：$1 \le x \le n, 1 \le y \le 1000$