У ряд вишикувалися $n$ учнів, де $i$-й зліва учень тримає табличку з числом $a_i$. Числа на табличках — різні цілі числа від $1$ до $n$.

Вони репетирують захід під назвою «Порівняння», який складається з $n - 1$ раундів. У кожному раунді двоє учнів, що наразі стоять на самому лівому краю ряду, виходять уперед і порівнюють числа на своїх табличках. Учень із більшим числом обирається (він не повертається до строю і не бере участі в наступних раундах), а учень із меншим числом повертається в самий правий кінець ряду.

Вам потрібно обробити $m$ операцій двох типів:

• Поміняти місцями таблички, які тримають учні на позиціях $x$ та $y$ зліва ($1 \le x < y \le n$);
• За заданими $l$ та $r$ ($1 \le l \le r < n$) змоделювати захід для поточного ряду учнів і обчислити суму чисел на табличках учнів, обраних із $l$-го по $r$-й раунд включно (після моделювання учні повертаються на свої позиції, які вони займали до цього запиту).

Вхідні дані

Перший рядок містить два цілі числа $n$ та $m$ ($2 \le n \le 10^5, 1 \le m \le 10^5$) — кількість учнів та кількість операцій відповідно.

Другий рядок містить $n$ різних цілих чисел $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), що позначають початкові числа на табличках учнів зліва направо.

Кожен із наступних $m$ рядків описує операцію в одному з двох форматів:

• C x y ($1 \le x < y \le n$): поміняти місцями таблички в руках учнів на позиціях $x$ та $y$ зліва;
• A l r ($1 \le l \le r < n$): знайти суму чисел на табличках учнів, обраних із $l$-го по $r$-й раунд, якщо змоделювати захід для поточного ряду.

Вихідні дані

Для кожної операції A l r виведіть в окремому рядку одне ціле число — відповідь на запит.

Приклад

Вхідні дані

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

Вихідні дані

8
8
10
12

Примітка

У першому запиті таблички зліва направо дорівнюють $[4, 3, 1, 2, 5]$. У чотирьох раундах обираються числа $4, 2, 5, 3$, тому сума з $3$-го по $4$-й раунд дорівнює $5 + 3 = 8$.

В останньому запиті таблички зліва направо дорівнюють $[3, 4, 5, 2, 1]$. У чотирьох раундах обираються числа $4, 5, 3, 2$, тому сума з $1$-го по $3$-й раунд дорівнює $4 + 5 + 3 = 12$.