$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$입니다.