P3396 Hash Collisions

As is well known, modular hashing produces collisions. For example, if the modulus $p=7$, then $4$ and $11$ collide.

B is very interested in hash collisions. He will give a sequence of positive integers $\text{value}$. Naturally, B will store these data into hash buckets. $\text{value}_k$ will be stored in the bucket $(k \bmod p)$. This creates many collisions. B will give many pairs $p$ and $x$, asking for the sum of numbers in bucket $x$ under modulus $p$. In addition, B may change $\text{value}_k$ at any time. Each change takes effect immediately. It is guaranteed that $1 \leq p < n$.

The first line contains two positive integers $n$, $m$, where $n$ is the length of the sequence, and $m$ is the number of operations by B. The second line contains $n$ positive integers, representing the initial sequence. Then $m$ lines follow. Each line starts with a character $\text{cmd}$, followed by two integers $x$, $y$. - If $\text{cmd}=\text{A}$, query the sum of numbers in bucket $y$ under modulus $x$. - If $\text{cmd}=\text{C}$, change $\text{value}_x$ to $y$.

For each query, output one positive integer as the answer.

#### Sample Explanation `A 2 1` has the answer `1+3+5+7+9=25`. `A 3 1` has the answer `20+4+7+10=41`. `A 5 0` has the answer `1+10=11`. #### Constraints For $10\%$ of the testdata, $n \leq 1000$, $m \leq 1000$. For $60\%$ of the testdata, $n \leq 100000$, $m \leq 100000$. For $100\%$ of the testdata, $n \leq 150000$, $m \leq 150000$. All testdata are valid, and $1 \leq \mathrm{value}_i \leq 1000$. Translated by ChatGPT 5