ישנם $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$.