Það eru $n$ nemendur í röð, þar sem $i$-ti nemandinn frá vinstri heldur á skilti með tölunni $a_i$. Tölurnar á skiltunum eru ólíkar heiltölur á bilinu $1$ til $n$.

Þau eru að æfa atriði sem kallast „Samanburður“ og samanstendur af $n - 1$ umferðum. Í hverri umferð stíga þeir tveir nemendur sem eru lengst til vinstri í röðinni fram og bera saman tölurnar á skiltunum sínum. Nemandinn með hærri töluna er valinn (og fer ekki aftur í röðina né tekur þátt í næstu umferðum), en nemandinn með lægri töluna fer aftur lengst til hægri í röðina.

Þú þarft að vinna úr $m$ aðgerðum af tveimur gerðum:

• Víxla skiltunum sem nemendurnir í sætum $x$ og $y$ frá vinstri halda á ($1 \le x < y \le n$);
• Gefin eru $l$ og $r$ ($1 \le l \le r < n$), herma eftir atriðinu með núverandi röð nemenda og reikna summu talnanna á skiltum þeirra nemenda sem eru valdir frá $l$-tu umferð til $r$-tu umferðar, báðar meðtaldar (eftir hermunina fara nemendurnir aftur á sína staði eins og þeir voru fyrir þessa fyrirspurn).

Inntak

Fyrsta línan inniheldur tvær heiltölur $n$ og $m$ ($2 \le n \le 10^5, 1 \le m \le 10^5$), sem tákna fjölda nemenda og fjölda aðgerða, í sömu röð.

Önnur línan inniheldur $n$ ólíkar heiltölur $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), sem tákna upphaflegu tölurnar á skiltunum sem nemendurnir halda á frá vinstri til hægri.

Hver af næstu $m$ línum lýsir aðgerð á öðru af eftirfarandi tveimur sniðum:

• C x y ($1 \le x < y \le n$): víxla skiltunum sem nemendurnir í sætum $x$ og $y$ frá vinstri halda á;
• A l r ($1 \le l \le r < n$): spyrja um summu talnanna á skiltum þeirra nemenda sem eru valdir frá $l$-tu umferð til $r$-tu umferðar ef atriðið er hermt með núverandi röð.

Úttak

Fyrir hverja A l r aðgerð skal prenta eina línu sem inniheldur heiltölu sem táknar svarið.

Dæmi

Inntak

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

Úttak

8
8
10
12

Athugasemd

Fyrir fyrstu fyrirspurnina eru skiltin frá vinstri til hægri $[4, 3, 1, 2, 5]$. Tölurnar sem eru valdar í umferðunum fjórum eru $4, 2, 5, 3$, þannig að summan frá $3$. umferð til $4$. umferðar er $5 + 3 = 8$.

Fyrir síðustu fyrirspurnina eru skiltin frá vinstri til hægri $[3, 4, 5, 2, 1]$. Tölurnar sem eru valdar í umferðunum fjórum eru $4, 5, 3, 2$, þannig að summan frá $1$. umferð til $3$. umferðar er $4 + 5 + 3 = 12$.