Det står $n$ elever oppstilt på en rekke, der den $i$-te eleven fra venstre holder et skilt med tallet $a_i$. Tallene på skiltene er forskjellige heltall mellom $1$ og $n$.

De øver på en aktivitet kalt «Sammenligning», som består av $n - 1$ runder. I hver runde trer de to elevene som for øyeblikket står helt til venstre i rekken frem og sammenligner tallene på skiltene sine. Eleven med det største tallet blir valgt ut (og går ikke tilbake til rekken eller deltar i påfølgende runder), mens eleven med det minste tallet går tilbake til plassen helt til høyre i rekken.

Du må behandle $m$ operasjoner av to typer:

• Bytt om skiltene som holdes av elevene på posisjonene $x$ og $y$ fra venstre ($1 \le x < y \le n$);
• Gitt $l$ og $r$ ($1 \le l \le r < n$), simuler aktiviteten med den nåværende rekken av elever og beregn summen av tallene på skiltene til elevene som blir valgt ut fra den $l$-te runden til og med den $r$-te runden (etter simuleringen går elevene tilbake til posisjonene de hadde før denne spørringen).

Inndata

Den første linjen inneholder to heltall $n$ og $m$ ($2 \le n \le 10^5, 1 \le m \le 10^5$), som representerer henholdsvis antallet elever og antallet operasjoner.

Den andre linjen inneholder $n$ forskjellige heltall $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), som representerer tallene som opprinnelig står på skiltene elevene holder fra venstre mot høyre.

Hver av de neste $m$ linjene beskriver en operasjon i ett av følgende to formater:

• C x y ($1 \le x < y \le n$): bytt om skiltene som holdes av elevene på posisjonene $x$ og $y$ fra venstre;
• A l r ($1 \le l \le r < n$): spør etter summen av tallene på skiltene til elevene som blir valgt ut fra den $l$-te runden til den $r$-te runden dersom aktiviteten simuleres med den nåværende rekken.

Utdata

For hver A l r-operasjon skal du skrive ut én enkelt linje med et heltall som representerer svaret.

Eksempel

Inndata

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

Utdata

8
8
10
12

Forklaring

For den første spørringen er skiltene fra venstre mot høyre $[4, 3, 1, 2, 5]$. Tallene som velges ut i de fire rundene er $4, 2, 5, 3$, så summen fra den $3$. runden til den $4$. runden er $5 + 3 = 8$.

For den siste spørringen er skiltene fra venstre mot høyre $[3, 4, 5, 2, 1]$. Tallene som velges ut i de fire rundene er $4, 5, 3, 2$, så summen fra den $1$. runden til den $3$. runden er $4 + 5 + 3 = 12$.