$n$ 人の生徒が一列に並んでおり、左から $i$ 番目の生徒は数 $a_i$ が書かれた札を持っています。札に書かれた数は $1$ から $n$ までの互いに異なる整数です。

彼らは「比較」というイベントのリハーサルを行っており、このイベントは $n - 1$ ラウンドからなります。各ラウンドでは、その時点で列の左端にいる 2 人の生徒が前に出て、持っている札の数を比較します。大きい方の数を持つ生徒が選出され（列には戻らず、以降のラウンドにも参加しません）、小さい方の数を持つ生徒は列の右端に戻ります。

次の 2 種類の操作を $m$ 回処理してください：

• 左から $x$ 番目と $y$ 番目の位置にいる生徒が持っている札を交換する（$1 \le x < y \le n$）；
• $l$ と $r$（$1 \le l \le r < n$）が与えられたとき、現在の生徒の並びでイベントをシミュレーションし、第 $l$ ラウンドから第 $r$ ラウンドまで（両端を含む）に選出された生徒の札に書かれた数の総和を求める（シミュレーション後、生徒たちはこのクエリの前の位置に戻ります）。

入力

最初の行には、それぞれ生徒の人数と操作の回数を表す 2 つの整数 $n$ と $m$ ($2 \le n \le 10^5, 1 \le m \le 10^5$) が与えられます。

2 行目には、最初に生徒が左から順に持っている札の数を表す $n$ 個の互いに異なる整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) が与えられます。

続く $m$ 行には、それぞれ次の 2 つの形式のいずれかで操作が記述されています：

• 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 操作について、答えを表す整数を 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

出力

8
8
10
12

ノート

最初のクエリでは、左から右への札は $[4, 3, 1, 2, 5]$ です。4 回のラウンドで選出される数は順に $4, 2, 5, 3$ なので、第 $3$ ラウンドから第 $4$ ラウンドまでの総和は $5 + 3 = 8$ です。

最後のクエリでは、左から右への札は $[3, 4, 5, 2, 1]$ です。4 回のラウンドで選出される数は順に $4, 5, 3, 2$ なので、第 $1$ ラウンドから第 $3$ ラウンドまでの総和は $4 + 5 + 3 = 12$ です。