Background

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

Problem Description

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$.

Input Format

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$.

Output Format

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

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

Hint

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