Hay $n$ estudiantes formados en una fila, donde el $i$-ésimo estudiante desde la izquierda sostiene un cartel con el número $a_i$. Los números en los carteles son enteros distintos entre $1$ y $n$.

Están ensayando una actividad llamada «Comparación», que consta de $n - 1$ rondas. En cada ronda, los dos estudiantes que se encuentran actualmente en el extremo izquierdo de la fila dan un paso al frente y comparan los números de sus carteles. El estudiante con el número mayor es seleccionado (y no regresa a la fila ni participa en las rondas siguientes), mientras que el estudiante con el número menor regresa al extremo derecho de la fila.

Debes procesar $m$ operaciones de dos tipos:

• Intercambiar los carteles que sostienen los estudiantes en las posiciones $x$ e $y$ desde la izquierda ($1 \le x < y \le n$);
• Dados $l$ y $r$ ($1 \le l \le r < n$), simular la actividad con la fila actual de estudiantes y calcular la suma de los números en los carteles de los estudiantes seleccionados desde la $l$-ésima ronda hasta la $r$-ésima ronda, inclusive (después de la simulación, los estudiantes regresan a las posiciones que tenían antes de esta consulta).

Entrada

La primera línea contiene dos enteros $n$ y $m$ ($2 \le n \le 10^5, 1 \le m \le 10^5$), que representan el número de estudiantes y el número de operaciones, respectivamente.

La segunda línea contiene $n$ enteros distintos $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), que representan los números inicialmente en los carteles que sostienen los estudiantes de izquierda a derecha.

Cada una de las siguientes $m$ líneas describe una operación en uno de los dos formatos siguientes:

• C x y ($1 \le x < y \le n$): intercambiar los carteles que sostienen los estudiantes en las posiciones $x$ e $y$ desde la izquierda;
• A l r ($1 \le l \le r < n$): consultar la suma de los números en los carteles de los estudiantes seleccionados desde la $l$-ésima ronda hasta la $r$-ésima ronda si se simula la actividad con la fila actual.

Salida

Para cada operación A l r, imprime una sola línea con un entero que represente la respuesta.

Ejemplo

Entrada

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

Salida

8
8
10
12

Nota

Para la primera consulta, los carteles de izquierda a derecha son $[4, 3, 1, 2, 5]$. Los números seleccionados en las cuatro rondas son $4, 2, 5, 3$, por lo que la suma desde la $3$-ra ronda hasta la $4$-ta ronda es $5 + 3 = 8$.

Para la última consulta, los carteles de izquierda a derecha son $[3, 4, 5, 2, 1]$. Los números seleccionados en las cuatro rondas son $4, 5, 3, 2$, por lo que la suma desde la $1$-ra ronda hasta la $3$-ra ronda es $4 + 5 + 3 = 12$.