1072 : บัญชาแห่งจำนวน (number)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 8 megabyte(s)

    คุณ และนักโบราณคดีหลบระเบิดมาได้อย่างเฉียดฉิว ทำให้เทพเจ้าแห่งตัวเลขตกใจเป็นอย่างมาก อย่างไรก็ดีก่อนที่เทพเจ้าจะยอมรับว่าคุณและนักโบราณคดีไม่ใช่ผู้ตั้งใจลบ หลู่ เป็นเพียงแค่หมู่คนที่จริงๆ แล้วมีสัมมาคารวะ เพียงแต่ยังไม่รู้กาลเทศะดีเท่านั้น เทพเจ้าต้องการทดสอบคุณเป็นขั้นสุดท้าย

    เทพเจ้ากำหนดให้มีลำดับจำนวนเต็ม N จำนวน แทนด้วย a₁,a₂,a₃,...,a_N โดยที่ 0 ≤ a_i ≤ 10⁹ และกำหนดให้มีปฏิบัติการกับลำดับของตัวเลขนี้ 4 ประเภทดังนี้

• การเวียนวนตัวเลข (a) เมื่อกำหนดค่าจำนวนเต็มบวก x และ y มาให้ หน้าที่ของคุณคือการสลับค่าของ a_x และ a_y (ค่า x และ y อาจเท่ากันได้)
• การจำแลงตัวเลข (b) เมื่อกำหนดจำนวนเต็มบวก x และ k หน้าที่ของคุณคือแทนค่า a_x ใหม่ด้วยค่า k ที่รับเข้ามา
• การปัดเป่าตัวเลข (c) เมื่อกำหนดจำนวนเต็มบวก x หน้าที่ของคุณคือแบ่งตัวเลขออกเป็นส่องกลุ่ม กลุ่มแรกคือตัวเลข x ตัวแรก และกลุ่มที่สองคือตัวเลข N - x ตัวที่เหลือ หลังจากนั้นให้เรียงตัวเลขทั้งสองกลุ่มจากหลังไปหน้าแล้วนำมาต่อกัน กล่าวคือ เปลี่ยนลำดับจาก  a₁,a₂,a₃,...,a_N  ให้เป็น a_x,a_x-1,a_x-2,...,a₂,a₁,a_n,a_n-1,a_n-2,...,a_x+2,a_x+1
• การออกดอกของตัวเลข (q) เมื่อกำหนดจำนวนเต็ม x หน้าที่ของคุณบอกเทพเจ้าว่า a_x มีค่าเท่าใด

งานของคุณ
    จงเขียนโปรแกรมรับลำดับตั้งต้นและรายการปฏิบัติการที่เทพเจ้าสั่งตามลำดับก่อนหลัง แล้วแสดงผลลัพธ์ตัวเลขของปฏิบัติการออกดอกของตัวเลข ออกมาตามลำดับในข้อมูลเข้า

ข้อมูลนำเข้า
    บรรทัดแรกมีจำนวนเต็ม N และ M (1 ≤ N, M ≤ 500,000) แสดงความยาวของลำดับตัวเลข และจำนวนปฏิบัติการตามลำดับ
    อีก N บรรทัดถัดมา มีข้อมูลของจำนวนเริ่มต้นในลำดับ  โดยในบรรทัดที่ i + 1 ของข้อมูลนำเข้าจะมีจำนวนเต็มหนึ่งตัว แทนค่า ai
    อีก M บรรทัดถัดมา มีข้อมูลของปฏิบัติการที่เทพเจ้าสั่งให้คุณทำ โดยแต่ละบรรทัดจะมีรูปแบบหนึ่งในสี่แบบดังต่อไปนี้

• “a x y”  โดย x, y คือจำนวนเต็มซึ่ง 1 ≤ x, y ≤ N หมายความว่าให้ทำการเวียนวนตัวเลขด้วยค่า x และ y ที่กำหนด
• “b x k”  โดย x เป็นจำนวนเต็มซึ่ง 1 ≤ x ≤ N และ k เป็นจำนวนเต็มซึ่ง 0 ≤ k ≤ 109 หมายความว่าให้ทำการจำแลงตัวเลขด้วยค่า  และ  ที่กำหนด
• “c x”  โดย x เป็นจำนวนเต็มซึ่ง 1 ≤ x ≤ N หมายความว่าใหทำการปัดเป่าตัวเลขด้วยค่า  ที่กำหนด
• “q x” โดย x เป็นจำนวนเต็มซึ่ง 1 ≤ x ≤ N หมายความว่าให้ทำการออกดอกตัวเลขโดยใช้ค่า  ที่กำหนด

ข้อมูลส่งออก
    มี D บรรทัดเมื่อ D คือจำนวนการออกดอกตัวเลขในข้อมูลเข้า โดยในบรรทัดที่ i ให้พิมพ์คำตอบของการออกดอกตัวเลขครั้งที่ i ตามลำดับก่อนหลังในข้อมูลเข้า

อธิบายตัวอย่างข้อมูลนำเข้า

ข้อมูลนำเข้า	ข้อมูลส่งออก	คำอธิบาย
5 6		รับค่า N = 5,M = 6
1		กำหนดค่า a1  = 1
3		กำหนดค่า a2  = 3
4		กำหนดค่า a3  = 4
5		กำหนดค่า a4  = 5
2		กำหนดค่า a5  = 2
q 3	4	แสดงค่า a3
b 3 6		ลำดับของจำนวนใหม่คือ 1 3 6 5 2
a 2 4		ลำดับของจำนวนใหม่คือ 1 5 6 3 2
q 2	5	แสดงค่า a2
c 1		ลำดับของจำนวนใหม่คือ 1 2 3 6 5
q 4	6	แสดงค่า a4

        50% ของชุดข้อมูลทดสอบ มีค่า N ≤ 5,000 และ M ≤ 5,000 และในทุกชุดข้อมูลทดสอบมีค่า N ≤ 500,000 และ M ≤ 500,000

ที่มา: การแข่งขัน YTOPC Challenge เมษายน 2552

ตัวอย่างข้อมูลนำเข้า	ตัวอย่างข้อมูลส่งออก
5 6 1 3 4 5 2 q 3 b 3 6 a 2 4 q 2 c 1 q 4	4 5 6

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้