哈希冲突

题目背景

此题约为 NOIP 提高组 Day2T2 难度。

题目描述

众所周知,模数的 hash 会产生冲突。例如,如果模的数 $p=7$,那么 $4$ 和 $11$ 便冲突了。 B 君对 hash 冲突很感兴趣。他会给出一个正整数序列 $\text{value}$。 自然,B 君会把这些数据存进 hash 池。第 $\text{value}_k$ 会被存进 $(k \mod p)$ 这个池。这样就能造成很多冲突。 B 君会给定许多个 $p$ 和 $x$,询问在模 $p$ 时,$x$ 这个池内 **数的总和**。 另外,B 君会随时更改 $\text{value}_k$。每次更改立即生效。 保证 ${1\leq p<n}$.

输入输出格式

输入格式


第一行,两个正整数 $n$, $m$,其中 $n$ 代表序列长度,$m$ 代表 B 君的操作次数。 第一行,$n$ 个正整数,代表初始序列。 接下来 $m$ 行,首先是一个字符 $\text{cmd}$,然后是两个整数 $x,y$。 - 若 $\text{cmd}=\text{A}$,则询问在模 $x$ 时,$y$ 池内 **数的总和**。 - 若 $\text{cmd}=\text{C}$,则将 $\text{value}_x$ 修改为 $y$。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

25
41
11

说明

#### 样例解释 `A 2 1` 的答案是 `1+3+5+7+9=25`. `A 3 1` 的答案是 `20+4+7+10=41`. `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 \text{value}_i \leq 1000$.