Бір қатарда $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$ болады.