W rzędzie ustawionych jest $n$ uczniów, przy czym $i$-ty uczeń od lewej trzyma tabliczkę z liczbą $a_i$. Liczby na tabliczkach są parami różnymi liczbami całkowitymi z przedziału od $1$ do $n$.

Uczniowie przeprowadzają próbę zabawy o nazwie „Porównanie”, która składa się z $n - 1$ rund. W każdej rundzie dwóch uczniów znajdujących się aktualnie najbardziej na lewo w rzędzie występuje przed szereg i porównuje liczby na swoich tabliczkach. Uczeń z większą liczbą zostaje wybrany (i nie wraca do rzędu ani nie bierze udziału w kolejnych rundach), natomiast uczeń z mniejszą liczbą wraca na sam koniec rzędu z prawej strony.

Musisz przetworzyć $m$ operacji dwóch typów:

• Zamień tabliczki trzymane przez uczniów na pozycjach $x$ oraz $y$ od lewej ($1 \le x < y \le n$);
• Dla danych $l$ oraz $r$ ($1 \le l \le r < n$) zasymuluj zabawę dla aktualnego ustawienia uczniów i oblicz sumę liczb na tabliczkach uczniów wybranych od $l$-tej do $r$-tej rundy włącznie (po symulacji uczniowie wracają na swoje pozycje sprzed tego zapytania).

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $m$ ($2 \le n \le 10^5, 1 \le m \le 10^5$), oznaczające odpowiednio liczbę uczniów oraz liczbę operacji.

Drugi wiersz zawiera $n$ parami różnych liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), oznaczających początkowe liczby na tabliczkach trzymanych przez uczniów od lewej do prawej.

Każdy z kolejnych $m$ wierszy opisuje operację w jednym z dwóch poniższych formatów:

• C x y ($1 \le x < y \le n$): zamień tabliczki trzymane przez uczniów na pozycjach $x$ oraz $y$ od lewej;
• A l r ($1 \le l \le r < n$): zapytaj o sumę liczb na tabliczkach uczniów wybranych od $l$-tej do $r$-tej rundy, gdyby przeprowadzić symulację zabawy dla aktualnego rzędu.

Wyjście

Dla każdej operacji A l r wypisz jeden wiersz zawierający liczbę całkowitą oznaczającą odpowiedź.

Przykład

Wejście

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

Wyjście

8
8
10
12

Uwaga

Dla pierwszego zapytania tabliczki od lewej do prawej to $[4, 3, 1, 2, 5]$. Liczby wybrane w czterech rundach to kolejno $4, 2, 5, 3$, więc suma od $3$-ciej do $4$-tej rundy wynosi $5 + 3 = 8$.

Dla ostatniego zapytania tabliczki od lewej do prawej to $[3, 4, 5, 2, 1]$. Liczby wybrane w czterech rundach to kolejno $4, 5, 3, 2$, więc suma od $1$-szej do $3$-ciej rundy wynosi $4 + 5 + 3 = 12$.