Клеопатра жолдарды жақсы көреді. Оған ұзындығы $n$ болатын $s$ жолы ($s[1], \dots, s[n]$ таңбаларынан тұратын) берілгенде, ол бірден оны сұрыптауға кіріседі. Сұрыптау барысында ол $s[i] \leftrightarrow s[i + 1]$ түріндегі алмастырулар тізбегін орындайды, мұндағы $i \in \{1, 2, \dots, n - 1\}$. Соңында ол сұрыпталған жолды қайтарады және жасалған барлық алмастырулардағы $i$ мәндерінің қосындысына тең алтын монеталар санын талап етеді (егер бірдей $i$ үшін алмастыру бірнеше рет жасалса, онда ол $i$ қосындыда қанша рет алмастырылса, сонша рет есептеледі). Клеопатра ысырапшыл емес: жолды сұрыптаудың барлық тәсілдерінің ішінен ол сұрыптау үшін алатын монеталар саны ең аз болатын тәсілді таңдайды.
Екатерина Медичи де жолдарды жақсы көреді. Оның ұзындығы $n$ болатын жолы бар және ол онымен ойнағысы келеді. Атап айтқанда, оны келесі амалдар қызықтырады:
- "
1 i c" — $s[i]$ элементін $c$-ға ауыстыру; - "
2 i j" — $s$ жолының $i$-ші таңбасынан $j$-ші таңбасына дейінгі (шеткілерін қоса алғанда, $i \le j$) ішкі жолының көшірмесін алып, оны сұрыптау, бұл ретте $s$ жолының таңбалары өзгеріссіз қалады. - "
3 i j" — $s$ жолының $i$-ші таңбасынан $j$-ші таңбасына дейінгі (шеткілерін қоса алғанда, $i \le j$) ішкі жолын қиып алып, оны сұрыптап, қайтадан $s$ жолындағы сол орынға қою.
Екатерина Медичи бірінші түрдегі сұраныстарды өзі орындай алады, бірақ екінші және үшінші түрдегі сұраныстар тым күрделі болғандықтан, ол олар үшін Клеопатраға жүгінеді. Бұл процедураның құнын бағалау кезінде Клеопатра $s$ жолындағы индекстерді ($i$-ден $j$-ге дейін) емес, ішкі жолдың басына қатысты индекстерді ($1$-ден $j - i + 1$-ге дейін) қосады.
Екатерина Медичи де ысырапшыл емес және өз бюджетін мұқият қадағалайды. Сондықтан оның Клеопатраға жасаған әрбір өтініші үшін Екатерина Медичидің қанша алтын монета жұмсайтынын есептеңіз.
Кіріс деректер
Кіріс деректердің бірінші жолында бір бүтін сан $t$ — тест жиынтықтарының саны берілген ($1 \le t \le 3 \cdot 10^5$). Әрбір тест жиынтығы үшін:
Бірінші жолда екі бүтін сан $n$ және $q$ — жолдың ұзындығы мен сұраныстар саны берілген ($1 \le n, q \le 3 \cdot 10^5$). Келесі жолда латын әліпбиінің $n$ бас әрпінен тұратын жол берілген. Келесі $q$ жол сұраныстарды сипаттайды. Әрбір сұраныс сипаттамасы үш түрдің біріне жатады:
- "
1 i c" — $s[i]$ таңбасын $c$-ға ауыстыру ($1 \le i \le n$; $c \in \{\text{A}, \text{B}, \dots, \text{Z}\}$); - "
2 i j" — $s$ жолын өзгеріссіз қалдырып, $s[i..j]$ ішкі жолын сұрыптау құнын табу ($1 \le i, j \le n$); - "
3 i j" — $s[i..j]$ ішкі жолын сұрыптау құнын табу, бұл ретте $s$ жолындағы $s[i..j]$ ішкі жолы сұрыпталған ішкі жолмен ауыстырылады ($1 \le i, j \le n$).
Әрбір тест жиынтығында екінші немесе үшінші түрдегі кем дегенде бір сұраныс болады.
Барлық тест жиынтықтары бойынша $n$ мәндерінің қосындысы $3 \cdot 10^5$-нен аспайды. Барлық тест жиынтықтары бойынша $q$ мәндерінің қосындысы $3 \cdot 10^5$-нен аспайды.
Шығыс деректер
Әрбір тест жиынтығы үшін бөлек жолдарда екінші және үшінші түрдегі барлық сұраныстардың жауаптарын, яғни әрбір сұрыптау үшін Клеопатра алатын монеталар санын шығарыңыз.
Мысалдар
Кіріс деректер 1
1 5 20 DBCAA 2 1 5 2 2 4 1 3 Z 2 1 3 3 1 5 2 1 5 1 5 A 3 2 4 2 1 5 1 1 C 2 1 2 3 4 5 2 3 5 1 2 B 2 1 5 3 1 1 2 1 1 1 4 D 2 1 5 3 1 5
Шығыс деректер 1
18 3 1 16 0 0 7 1 1 1 9 0 0 3 3
Кіріс деректер 2
3 3 5 CBA 2 1 3 3 1 3 2 1 3 1 2 C 2 1 2 5 5 ABCDE 2 2 5 1 5 A 2 1 5 3 1 5 2 1 5 6 5 YYYYYY 2 1 6 1 3 A 2 1 6 3 2 5 2 1 6
Шығыс деректер 2
4 4 0 0 0 9 9 0 0 3 1 1
Ескертпе
Бірінші мысалды қарастырайық. Онда бастапқы жол — "DBCAA". Барлық 20 сұранысты ретімен қарап шығайық:
- Сұраныс "
2 1 5". Ағымдағы жол: "DBCAA". Ішкі жол $t[1..5]$ = "DBCAA", жауабы: 18. Жол өзгермейді. - Сұраныс "
2 2 4". Жол: "DBCAA". Ішкі жол $t[2..4]$ = "BCA", жауабы: 3. Жол өзгермейді. - Сұраныс "
1 3 Z". Жаңарту: $t[3] \leftarrow$ "Z". Бұрын "DBCAA", қазір "DBZAA". - Сұраныс "
2 1 3". Жол: "DBZAA". Ішкі жол $t[1..3]$ = "DBZ", жауабы: 1. Жол өзгермейді. - Сұраныс "
3 1 5". Жол: "DBZAA". Ішкі жол $t[1..5]$ = "DBZAA", жауабы: 16. Өзгерістен кейін ішкі жолды сұрыптау: "DBZAA" $\rightarrow$ "AABDZ". Жол "AABDZ" болды. - Сұраныс "
2 1 5". Жол: "AABDZ". Ішкі жол "AABDZ", жауабы: 0. Жол өзгермейді. - Сұраныс "
1 5 A". Бұрын "AABDZ", қазір "AABDA". - Сұраныс "
3 2 4". Жол: "AABDA". Ішкі жол $t[2..4]$ = "ABD", жауабы: 0. Сұрыптаудан кейін "ABD" өзгермейді, жол "AABDA" күйінде қалады. - Сұраныс "
2 1 5". Жол: "AABDA". Ішкі жол "AABDA", жауабы: 7. Жол өзгермейді. - Сұраныс "
1 1 C". Бұрын "AABDA", қазір "CABDA". - Сұраныс "
2 1 2". Жол: "CABDA". Ішкі жол $t[1..2]$ = "CA", жауабы: 1. Жол өзгермейді. - Сұраныс "
3 4 5". Жол: "CABDA". Ішкі жол $t[4..5]$ = "DA", жауабы: 1. Өзгерістен кейін: "DA" $\rightarrow$ "AD". Жол "CABAD" болды. - Сұраныс "
2 3 5". Жол: "CABAD". Ішкі жол $t[3..5]$ = "BAD", жауабы: 1. Жол өзгермейді. - Сұраныс "
1 2 B". Бұрын "CABAD", қазір "CBBAD". - Сұраныс "
2 1 5". Жол: "CBBAD". Ішкі жол "CBBAD", жауабы: 9. Жол өзгермейді. - Сұраныс "
3 1 1". Жол: "CBBAD". Ішкі жол $t[1..1]$ = "C", жауабы: 0. Ұзындығы 1 жолды сұрыптау ештеңені өзгертпейді, жол "CBBAD" күйінде қалады. - Сұраныс "
2 1 1". Жол: "CBBAD". Ішкі жол $t[1..1]$ = "C", жауабы: 0. Жол өзгермейді. - Сұраныс "
1 4 D". Бұрын "CBBAD", қазір "CBBDD". - Сұраныс "
2 1 5". Жол: "CBBDD". Ішкі жол $t[1..5]$ = "CBBDD", жауабы: 3. Жол өзгермейді. - Сұраныс "
3 1 5". Жол: "CBBDD". Ішкі жол $t[1..5]$ = "CBBDD", жауабы: 3. Өзгерістен кейін: "CBBDD" $\rightarrow$ "BBCDD". Соңғы жол — "BBCDD".