#4697. 猪

内存限制:2 MiB 时间限制:10 Sec

题目描述

红学姐和黄学长是好朋友。红学姐有一只宠物,叫魔法猪。黄学长也有一只宠物,叫小奇。有 n 个猪圈排成一排
,魔法猪藏在某个猪圈中。为了找到魔法猪,小奇会向你询问一些猪圈中猪的个数和。在询问的过程中,魔法猪可
能会释放魔法来改变这些猪圈。
共有 m 次操作。每次操作是以下三种之一。
Q x y 询问从左到右第 x 个猪圈到第 y 个猪圈中猪的个数和。
C x y 将从左到右第 x 个猪圈中猪的个数变为 y。
M x y 将从左到右第 x 个猪圈移动到第 y 个猪圈的位置,并将第 y 个猪圈到第 x-1 个猪圈全部右移一格。保证
 x>y。保证任何时候每个猪圈中猪的数量在 0 至 1000000 之间。

输入格式

第一行包含两个整数 n,m,其值均小于等于10^5
第二行 n 个整数表示从左到右每个猪圈中猪的个数。
接下来 m 行每行一个操作。

输出格式

对于每个询问操作,输出一行一个整数表示答案。

样例

样例输入


			
5 10
1 2 3 4 5
Q 2 4
M 4 2
C 3 10
C 1 4
Q 1 3
Q 3 5
M 5 3
Q 1 3
C 4 1
Q 1 5

样例输出


			
9
18
18
13
17

数据范围与提示