Rivissä seisoo $n$ oppilasta, missä vasemmalta lukien $i$-s oppilas pitää kylttiä, jossa on luku $a_i$. Kylteissä olevat luvut ovat erisuuria kokonaislukuja väliltä $1$ ja $n$.

He harjoittelevat ”Vertailu”-nimistä ohjelmanumeroa, joka koostuu $n - 1$ kierroksesta. Jokaisella kierroksella kaksi sillä hetkellä rivin vasemmassa reunassa olevaa oppilasta astuu esiin ja vertaa kylttiensä lukuja. Suuremman luvun omaava oppilas valitaan (eikä hän palaa riviin tai osallistu seuraaville kierroksille), kun taas pienemmän luvun omaava oppilas siirtyy rivin oikeaan laitaan.

Sinun tulee käsitellä $m$ kahden eri tyypin operaatiota:

• Vaihda vasemmalta lukien paikoissa $x$ ja $y$ olevien oppilaiden kyltit keskenään ($1 \le x < y \le n$);
• Annettuna $l$ ja $r$ ($1 \le l \le r < n$), simuloi ohjelmanumero nykyisellä oppilasrivillä ja laske kierroksesta $l$ kierrokseen $r$ (molemmat mukaan lukien) valittujen oppilaiden kylteissä olevien lukujen summa (simuloinnin jälkeen oppilaat palaavat paikoilleen, joilla he olivat ennen tätä kyselyä).

Syöte

Ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $m$ ($2 \le n \le 10^5, 1 \le m \le 10^5$), jotka kuvaavat oppilaiden lukumäärää ja operaatioiden lukumäärää.

Toinen rivi sisältää $n$ erisuurta kokonaislukua $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), jotka kuvaavat oppilaiden aluksi pitämissä kylteissä olevia lukuja vasemmalta oikealle.

Jokainen seuraavista $m$ rivistä kuvaa operaation jommassakummassa seuraavista kahdesta muodosta:

• C x y ($1 \le x < y \le n$): vaihda vasemmalta lukien paikoissa $x$ ja $y$ olevien oppilaiden kyltit keskenään;
• A l r ($1 \le l \le r < n$): kysy kierroksesta $l$ kierrokseen $r$ valittujen oppilaiden kylttien lukujen summaa, jos ohjelmanumero simuloidaan nykyisellä rivillä.

Tuloste

Tulosta jokaista A l r -operaatiota kohden yksi rivi, joka sisältää vastausta kuvaavan kokonaisluvun.

Esimerkki

Syöte

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

Tuloste

8
8
10
12

Huomautus

Ensimmäisessä kyselyssä kyltit vasemmalta oikealle ovat $[4, 3, 1, 2, 5]$. Neljällä kierroksella valitut luvut ovat $4, 2, 5, 3$, joten summa $3$. kierroksesta $4$. kierrokseen on $5 + 3 = 8$.

Viimeisessä kyselyssä kyltit vasemmalta oikealle ovat $[3, 4, 5, 2, 1]$. Neljällä kierroksella valitut luvut ovat $4, 5, 3, 2$, joten summa $1$. kierroksesta $3$. kierrokseen on $4 + 5 + 3 = 12$.