Terdapat $n$ siswa yang berbaris dalam satu barisan, di mana siswa ke-$i$ dari kiri memegang papan bertuliskan angka $a_i$. Angka-angka pada papan tersebut adalah bilangan bulat berbeda antara $1$ dan $n$.

Mereka sedang melakukan gladi bersih untuk sebuah kegiatan bernama "Perbandingan", yang terdiri dari $n - 1$ babak. Pada setiap babak, dua siswa yang saat ini berada paling kiri di dalam barisan maju ke depan dan membandingkan angka pada papan mereka. Siswa dengan angka yang lebih besar akan terpilih (dan tidak kembali ke barisan ataupun berpartisipasi dalam babak-babak berikutnya), sedangkan siswa dengan angka yang lebih kecil kembali ke ujung paling kanan barisan.

Anda perlu memproses $m$ operasi dari dua jenis berikut:

• Tukar papan yang dipegang oleh siswa pada posisi $x$ dan $y$ dari kiri ($1 \le x < y \le n$);
• Diberikan $l$ dan $r$ ($1 \le l \le r < n$), simulasikan kegiatan tersebut dengan barisan siswa saat ini dan hitung jumlah angka pada papan dari siswa-siswa yang terpilih mulai dari babak ke-$l$ hingga babak ke-$r$, inklusif (setelah simulasi selesai, para siswa kembali ke posisi mereka sebelum kueri ini).

Masukan

Baris pertama berisi dua bilangan bulat $n$ dan $m$ ($2 \le n \le 10^5, 1 \le m \le 10^5$), yang masing-masing menyatakan jumlah siswa dan jumlah operasi.

Baris kedua berisi $n$ bilangan bulat berbeda $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), yang menyatakan angka awal pada papan yang dipegang oleh para siswa dari kiri ke kanan.

Masing-masing dari $m$ baris berikutnya menjelaskan sebuah operasi dalam salah satu dari dua format berikut:

• C x y ($1 \le x < y \le n$): tukar papan yang dipegang oleh siswa pada posisi $x$ dan $y$ dari kiri;
• A l r ($1 \le l \le r < n$): tanyakan jumlah angka pada papan dari siswa-siswa yang terpilih mulai dari babak ke-$l$ hingga babak ke-$r$ jika kegiatan disimulasikan dengan barisan saat ini.

Keluaran

Untuk setiap operasi A l r, keluarkan satu baris yang berisi sebuah bilangan bulat yang menyatakan jawabannya.

Contoh

Masukan

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

Keluaran

8
8
10
12

Catatan

Untuk kueri pertama, papan dari kiri ke kanan adalah $[4, 3, 1, 2, 5]$. Angka yang terpilih dalam empat babak tersebut adalah $4, 2, 5, 3$, sehingga jumlah dari babak ke-$3$ hingga babak ke-$4$ adalah $5 + 3 = 8$.

Untuk kueri terakhir, papan dari kiri ke kanan adalah $[3, 4, 5, 2, 1]$. Angka yang terpilih dalam empat babak tersebut adalah $4, 5, 3, 2$, sehingga jumlah dari babak ke-$1$ hingga babak ke-$3$ adalah $4 + 5 + 3 = 12$.