Es stehen $n$ Schüler in einer Reihe, wobei der $i$-te Schüler von links ein Schild mit der Zahl $a_i$ hält. Die Zahlen auf den Schildern sind paarweise verschiedene ganze Zahlen zwischen $1$ und $n$.

Sie proben eine Aktivität namens „Vergleich“, die aus $n - 1$ Runden besteht. In jeder Runde treten die beiden Schüler, die sich aktuell ganz links in der Reihe befinden, vor und vergleichen die Zahlen auf ihren Schildern. Der Schüler mit der größeren Zahl wird ausgewählt (und kehrt nicht in die Reihe zurück und nimmt auch nicht an nachfolgenden Runden teil), während der Schüler mit der kleineren Zahl ganz nach rechts ans Ende der Reihe zurückkehrt.

Sie müssen $m$ Operationen von zwei Typen verarbeiten:

• Vertauschen Sie die Schilder der Schüler an den Positionen $x$ und $y$ von links ($1 \le x < y \le n$);
• Gegeben $l$ und $r$ ($1 \le l \le r < n$), simulieren Sie die Aktivität mit der aktuellen Schülerreihe und berechnen Sie die Summe der Zahlen auf den Schildern der Schüler, die von der $l$-ten Runde bis einschließlich zur $r$-ten Runde ausgewählt wurden (nach der Simulation kehren die Schüler an ihre Positionen vor dieser Anfrage zurück).

Eingabe

Die erste Zeile enthält zwei ganze Zahlen $n$ und $m$ ($2 \le n \le 10^5, 1 \le m \le 10^5$), die die Anzahl der Schüler bzw. die Anzahl der Operationen darstellen.

Die zweite Zeile enthält $n$ paarweise verschiedene ganze Zahlen $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), die die anfänglichen Zahlen auf den Schildern der Schüler von links nach rechts darstellen.

Jede der nächsten $m$ Zeilen beschreibt eine Operation in einem der beiden folgenden Formate:

• C x y ($1 \le x < y \le n$): Vertauschen Sie die Schilder der Schüler an den Positionen $x$ und $y$ von links;
• A l r ($1 \le l \le r < n$): Fragen Sie die Summe der Zahlen auf den Schildern der von der $l$-ten bis zur $r$-ten Runde ausgewählten Schüler ab, wenn die Aktivität mit der aktuellen Reihe simuliert wird.

Ausgabe

Geben Sie für jede Operation A l r eine einzige Zeile mit einer ganzen Zahl aus, die die Antwort darstellt.

Beispiel

Eingabe

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

Ausgabe

8
8
10
12

Hinweis

Für die erste Anfrage lauten die Schilder von links nach rechts $[4, 3, 1, 2, 5]$. Die in den vier Runden ausgewählten Zahlen sind $4, 2, 5, 3$, sodass die Summe von der $3$. Runde bis zur $4$. Runde $5 + 3 = 8$ beträgt.

Für die letzte Anfrage lauten die Schilder von links nach rechts $[3, 4, 5, 2, 1]$. Die in den vier Runden ausgewählten Zahlen sind $4, 5, 3, 2$, sodass die Summe von der $1$. Runde bis zur $3$. Runde $4 + 5 + 3 = 12$ beträgt.