Il y a $n$ élèves alignés sur une rangée, où le $i$-ème élève en partant de la gauche tient une pancarte avec le numéro $a_i$. Les numéros sur les pancartes sont des entiers distincts compris entre $1$ et $n$.

Ils répètent une activité appelée « Comparaison », qui consiste en $n - 1$ manches. À chaque manche, les deux élèves actuellement tout à gauche de la file s'avancent et comparent les numéros inscrits sur leurs pancartes. L'élève ayant le plus grand numéro est sélectionné (et ne retourne pas dans la file ni ne participe aux manches suivantes), tandis que l'élève ayant le plus petit numéro retourne tout à droite de la file.

Vous devez traiter $m$ opérations de deux types :

• Échanger les pancartes tenues par les élèves aux positions $x$ et $y$ en partant de la gauche ($1 \le x < y \le n$) ;
• Étant donné $l$ et $r$ ($1 \le l \le r < n$), simuler l'activité avec la file actuelle d'élèves et calculer la somme des numéros sur les pancartes des élèves sélectionnés de la $l$-ème manche à la $r$-ème manche incluse (après la simulation, les élèves reprennent leurs positions d'avant cette requête).

Entrée

La première ligne contient deux entiers $n$ et $m$ ($2 \le n \le 10^5, 1 \le m \le 10^5$), représentant respectivement le nombre d'élèves et le nombre d'opérations.

La deuxième ligne contient $n$ entiers distincts $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), représentant les numéros initialement inscrits sur les pancartes tenues par les élèves de gauche à droite.

Chacune des $m$ lignes suivantes décrit une opération sous l'un des deux formats suivants :

• C x y ($1 \le x < y \le n$) : échanger les pancartes tenues par les élèves aux positions $x$ et $y$ en partant de la gauche ;
• A l r ($1 \le l \le r < n$) : demander la somme des numéros sur les pancartes des élèves sélectionnés de la $l$-ème manche à la $r$-ème manche si l'activité est simulée avec la file actuelle.

Sortie

Pour chaque opération A l r, affichez une seule ligne contenant un entier représentant la réponse.

Exemple

Entrée

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

Sortie

8
8
10
12

Note

Pour la première requête, les pancartes de gauche à droite sont $[4, 3, 1, 2, 5]$. Les numéros sélectionnés lors des quatre manches sont $4, 2, 5, 3$, donc la somme de la $3$-ème manche à la $4$-ème manche est $5 + 3 = 8$.

Pour la dernière requête, les pancartes de gauche à droite sont $[3, 4, 5, 2, 1]$. Les numéros sélectionnés lors des quatre manches sont $4, 5, 3, 2$, donc la somme de la $1$-ère manche à la $3$-ème manche est $4 + 5 + 3 = 12$.