题目描述

给定长度为 $n$ 的正整数序列 $a_1,\dots,a_n$，处理 $m$ 个操作：

• A x y：查询所有满足 $i\equiv y\pmod x$ 的下标对应元素之和 $\sum a_i$；
• C x y：单点修改，令 $a_x\gets y$。

对于 A x y，保证 $0\le y<x$。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个正整数。

接下来 $m$ 行，每行 A x y 或 C x y。

输出格式

对每个 A x y 操作输出一行，表示对应元素之和。

样例

10 4
1 2 3 4 5 6 7 8 9 10
A 2 1
A 3 0
C 3 10
A 3 0

25
18
25

数据范围

$1\le n,m\le 1.5\times10^5$，$1\le a_i\le 1000$，$0\le y<x\le n$。

C x y 中 $1\le x\le n$，$1\le y\le 1000$。