В ряд выстроились $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$.