Có $n$ học sinh xếp thành một hàng ngang, trong đó học sinh thứ $i$ tính từ bên trái cầm một tấm biển ghi số $a_i$. Các số trên các tấm biển là các số nguyên phân biệt từ $1$ đến $n$.

Họ đang tổng duyệt một hoạt động có tên là "So sánh" gồm $n - 1$ vòng. Trong mỗi vòng, hai học sinh hiện đang ở ngoài cùng bên trái của hàng bước lên phía trước và so sánh số trên tấm biển của mình. Học sinh có số lớn hơn sẽ được chọn (và không quay lại hàng cũng như không tham gia vào các vòng tiếp theo), trong khi học sinh có số nhỏ hơn sẽ quay về vị trí ngoài cùng bên phải của hàng.

Bạn cần xử lý $m$ thao tác thuộc hai loại:

• Hoán đổi tấm biển của hai học sinh ở vị trí $x$ và $y$ tính từ bên trái ($1 \le x < y \le n$);
• Cho $l$ và $r$ ($1 \le l \le r < n$), mô phỏng hoạt động với hàng học sinh hiện tại và tính tổng các số trên tấm biển của những học sinh được chọn từ vòng thứ $l$ đến vòng thứ $r$ (sau khi mô phỏng, các học sinh trở lại vị trí của mình trước truy vấn này).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($2 \le n \le 10^5, 1 \le m \le 10^5$), lần lượt biểu thị số lượng học sinh và số lượng thao tác.

Dòng thứ hai chứa $n$ số nguyên phân biệt $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), biểu thị các số ban đầu trên tấm biển của các học sinh từ trái sang phải.

Mỗi dòng trong $m$ dòng tiếp theo mô tả một thao tác theo một trong hai định dạng sau:

• C x y ($1 \le x < y \le n$): hoán đổi tấm biển của hai học sinh ở vị trí $x$ và $y$ tính từ bên trái;
• A l r ($1 \le l \le r < n$): truy vấn tổng các số trên tấm biển của những học sinh được chọn từ vòng thứ $l$ đến vòng thứ $r$ nếu mô phỏng hoạt động với hàng hiện tại.

Dữ liệu ra

Với mỗi thao tác A l r, in ra một dòng chứa một số nguyên biểu thị đáp án.

Ví dụ

Dữ liệu vào

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

Dữ liệu ra

8
8
10
12

Ghi chú

Đối với truy vấn đầu tiên, các tấm biển từ trái sang phải là $[4, 3, 1, 2, 5]$. Các số được chọn trong bốn vòng lần lượt là $4, 2, 5, 3$, vì vậy tổng từ vòng thứ $3$ đến vòng thứ $4$ là $5 + 3 = 8$.

Đối với truy vấn cuối cùng, các tấm biển từ trái sang phải là $[3, 4, 5, 2, 1]$. Các số được chọn trong bốn vòng lần lượt là $4, 5, 3, 2$, vì vậy tổng từ vòng thứ $1$ đến vòng thứ $3$ là $4 + 5 + 3 = 12$.