มีนักเรียน $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$