小 J 正在为一项活动进行彩排。现在有 $n$ 名学生排成一排，每人手里拿着一块写有数字的牌子。从左到右第 $i$ 名学生手里的牌子上的数字为 $a_i$。牌子上的数字是 $1$ 到 $n$ 之间的互不相同的整数。

现在要进行一次“比较”活动彩排。该活动共进行 $n - 1$ 轮。在每一轮中，最左边的两名学生会走上前，然后比较他们牌子上的数字。数字较大的学生将被选中，而数字较小的学生将回到队列的最右端。需要注意的是，被选中的学生不会回到队列中，且不参与后续轮次的比较。

小 J 想知道在不同的数字排列下，每一轮中谁会被选中。他将进行 $m$ 次操作，每次操作为以下两种类型之一：

• 选择两个位置 $x, y$ 满足 $1 \le x < y \le n$，然后交换第 $x$ 名和第 $y$ 名学生手里的牌子；
• 给定两个参数 $l, r$ 满足 $1 \le l \le r < n$，模拟一次“比较”活动，并计算在第 $l$ 轮到第 $r$ 轮之间被选中的学生牌子上的数字之和。模拟结束后，所有学生将回到他们原本的位置。

输入格式

输入的第一行包含两个整数 $n, m$ ($2 \le n \le 10^5, 1 \le m \le 10^5$)，分别表示学生的数量和操作的数量。

下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)，表示每位学生手里牌子上的初始数字。保证所有的 $a_i$ 互不相同。

接下来的 $m$ 行，每行包含一个字符和两个整数，表示一次操作。

• 如果输入格式为 C x y，表示交换第 $x$ 名和第 $y$ 名学生手里的牌子，保证 $1 \le x < y \le n$；
• 如果输入格式为 A l r，表示模拟一次“比较”活动，并计算第 $l$ 轮到第 $r$ 轮之间被选中的数字之和，保证 $1 \le l \le r < n$。

输出格式

对于每次模拟操作，在新的一行中输出一个整数，表示答案。

样例

输入样例 1

5 6
4 3 1 2 5
A 3 4
C 1 2
A 3 4
A 2 4
C 3 5
A 1 3

输出样例 1

8
8
10
12

说明

在第一次模拟操作中，学生手里的数字依次为 $[4, 3, 1, 2, 5]$。在四轮比较中，被选中的数字依次为 $4, 2, 5, 3$，因此第 $3$ 轮到第 $4$ 轮之间被选中的数字之和为 $5 + 3 = 8$。

在最后一次模拟操作中，学生手里的数字依次为 $[3, 4, 5, 2, 1]$。在四轮比较中，被选中的数字依次为 $4, 5, 3, 2$，因此第 $1$ 轮到第 $3$ 轮之间被选中的数字之和为 $4 + 5 + 3 = 12$。