يوجد $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$.