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