哈希冲突

题目背景

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

题目描述

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

输入输出格式

输入格式


第一行,两个正整数`n,m`,其中`n`代表序列长度,`m`代表B君的操作次数。 第一行,`n`个正整数,代表初始序列。 接下来`m`行,首先是一个字符`cmd`,然后是两个整数`x,y`。 - 若`cmd='A'`,则询问在模`x`时,`y`池内**数的总和**。 - 若`cmd='C'`,则将`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<=1000,m<=1000`. 对于`60%`的数据,有`n<=100000.m<=100000`. 对于`100%`的数据,有`n<=150000,m<=150000`. 保证所有数据合法,且`1<=value[i]<=1000`.