คลีโอพัตราหลงใหลในสตริง เมื่อเธอได้รับสตริง $s$ ความยาว $n$ (ประกอบด้วยอักขระ $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[i..j]$ โดยที่สตริง $s$ ไม่เปลี่ยนแปลง ($1 \le i, j \le n$); - "
3 i j" — หาค่าใช้จ่ายในการเรียงลำดับสตริงย่อย $s[i..j]$ โดยที่สตริงย่อย $s[i..j]$ ในสตริง $s$ จะถูกแทนที่ด้วยสตริงย่อยที่เรียงลำดับแล้ว ($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"