有 $n$ 位同學排成一行，從左邊數起第 $i$ 位同學手入面攞住一個寫住數字 $a_i$ 嘅牌。牌上面嘅數字係 $1$ 到 $n$ 之間互不相同嘅整數。

佢哋緊喺度彩排一個叫做「比較」嘅活動，呢個活動由 $n - 1$ 輪組成。喺每一輪入面，當前排喺最左邊嘅兩位同學會行出嚟，比較佢哋牌上面嘅數字。數字較大嘅同學會被選中（唔會再返去隊伍入面，亦唔會參加之後嘅輪次），而數字較細嘅同學就會返去隊伍嘅最右邊。

你需要處理 $m$ 次以下兩種類型嘅操作：

• 交換從左邊數起第 $x$ 個同第 $y$ 個位置嘅同學手中嘅牌（$1 \le x < y \le n$）；
• 畀定 $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$），從左到右表示同學最初攞住嘅牌上面嘅數字。

接下來 $m$ 行，每行按以下兩種格式之一描述一次操作：

• C x y（$1 \le x < y \le n$）：交換從左邊數起第 $x$ 個同第 $y$ 個位置嘅同學手中嘅牌；
• A l r（$1 \le l \le r < n$）：詢問如果用當前隊伍模擬活動，從第 $l$ 輪到第 $r$ 輪被選中嘅同學手中嘅牌上面嘅數字總和。

輸出格式

對於每次 A l r 操作，輸出一行包含一個整數，表示答案。

範例

輸入

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

輸出

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