Ci sono $n$ studenti in fila, dove l'$i$-esimo studente da sinistra tiene un cartello con il numero $a_i$. I numeri sui cartelli sono interi distinti compresi tra $1$ e $n$.

Stanno provando un'attività chiamata "Confronto", che consiste in $n - 1$ turni. In ogni turno, i due studenti attualmente all'estrema sinistra della fila fanno un passo avanti e confrontano i numeri sui loro cartelli. Lo studente con il numero maggiore viene selezionato (e non torna nella fila né partecipa ai turni successivi), mentre lo studente con il numero minore torna all'estrema destra della fila.

Devi elaborare $m$ operazioni di due tipi:

• Scambiare i cartelli tenuti dagli studenti nelle posizioni $x$ e $y$ da sinistra ($1 \le x < y \le n$);
• Dati $l$ e $r$ ($1 \le l \le r < n$), simulare l'attività con la fila attuale di studenti e calcolare la somma dei numeri sui cartelli degli studenti selezionati dal $l$-esimo turno al $r$-esimo turno inclusi (dopo la simulazione, gli studenti tornano alle posizioni che occupavano prima di questa query).

Input

La prima riga contiene due interi $n$ e $m$ ($2 \le n \le 10^5, 1 \le m \le 10^5$), che rappresentano rispettivamente il numero di studenti e il numero di operazioni.

La seconda riga contiene $n$ interi distinti $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), che rappresentano i numeri inizialmente presenti sui cartelli tenuti dagli studenti da sinistra a destra.

Ciascuna delle successive $m$ righe descrive un'operazione in uno dei due formati seguenti:

• C x y ($1 \le x < y \le n$): scambia i cartelli tenuti dagli studenti nelle posizioni $x$ e $y$ da sinistra;
• A l r ($1 \le l \le r < n$): chiedi la somma dei numeri sui cartelli degli studenti selezionati dal $l$-esimo turno al $r$-esimo turno se l'attività viene simulata con la fila attuale.

Output

Per ogni operazione A l r, stampa una singola riga contenente un intero che rappresenta la risposta.

Esempio

Input

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

Output

8
8
10
12

Nota

Per la prima query, i cartelli da sinistra a destra sono $[4, 3, 1, 2, 5]$. I numeri selezionati nei quattro turni sono $4, 2, 5, 3$, quindi la somma dal $3$° turno al $4$° turno è $5 + 3 = 8$.

Per l'ultima query, i cartelli da sinistra a destra sono $[3, 4, 5, 2, 1]$. I numeri selezionati nei quattro turni sono $4, 5, 3, 2$, quindi la somma dal $1$° turno al $3$° turno è $4 + 5 + 3 = 12$.