题目描述

红学姐和黄学长是好朋友。红学姐有一只宠物，叫魔法猪。黄学长也有一只宠物，叫小奇。有 $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