题目描述

众所周知，模数的 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$行，首先是一个字符$ ext{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$.