Giải bài toán bằng Python hoặc C++

Các bạn đã tham gia trại hè Tin học Miền Trung – Tây Nguyên tại Quy Nhơn vừa qua hẳn không thể quên Phao Chuối – trò chơi mạo hiểm thử thách sự không sợ sóng biển làm khiếp sợ vị giáo sư đáng kính của chúng ta. Nhưng nay GSPVH đã khôn lớn, trưởng thành, không còn là đứa con nít 9475 ngày tuổi hôm nào, nên GSPVH quyết định cùng các bạn học sinh Quảng Ngãi đi trải nghiệm phao chuối một lần nữa.

Chiếc phao chuối tại Lý Sơn lần này có n vị trí ngồi, các vị trí ngồi được đánh số từ 1 đến n theo thứ tự từ đầu tới đuôi: vị trí thứ 1 ở đầu chuối, vị trí thứ n ở đuôi chuối và với mọi 1≤i≤n−1, vị trí thứ ii và thứ $i + 1% ở cạnh nhau.

Do đã tìm hiểu rất kỹ chiếc phao chuối trước chuyến đi, GSPVH nhận ra rằng, mỗi vị trí ngồi có một độ an toàn nhất định và không có hai vị trí ngồi nào có cùng độ an toàn. Nhờ đó, độ an toàn của nn vị trí ngồi có thể được biểu diễn bởi một hoán vị p1​,p2​,…,pn​ của các số nguyên từ 1 đến n. Vị trí ngồi thứ ii an toàn hơn vị trí ngồi thứ j khi và chỉ khi pi​<pj​; vị trí b có pb​=1 là vị trí ngồi an toàn nhất, vị trí w có pw​=n là vị trí kém an toàn nhất. Cũng vì rất am hiểu về phao chuối, GSPVH tìm ra vị trí ngồi ưa thích của mình là vị trí f.

GSPVH dẫn theo n−1 bạn học sinh của trường chuyên Lê Khiết đi chơi phao chuối. Coi GSPVH là người số 1 và n−1 bạn còn lại được đánh số từ 2 đến n. Toàn bộ nn người sẽ lần lượt bước lên phao chuối và ngồi vào một vị trí nào đó, quy trình chọn vị trí ngồi của nhóm người như sau:

• Trước hết, toàn bộ nn vị trí trên phao chuối đều trống.
• Đầu tiên, GSPVH (người thứ 1) ngồi vào vị trí ưa thích của mình là vị trí thứ f.
• Tiếp theo, lần lượt các bạn từ bạn thứ 2 đến bạn thứ nn chọn cho mình một vị trí trên phao chuối để ngồi. Tất cả các bạn đều chọn vị trí ngồi theo chiến lược sau:
  • Mỗi bạn luôn ngồi vào một vị trí còn trống tại thời điểm đó.
  • Mỗi bạn luôn ngồi vào một vị trí bên cạnh một vị trí đã có người ngồi trước đó.
  • Mỗi bạn luôn ngồi vào vị trí an toàn nhất trong các vị trí thoả mãn hai điều kiện trên.

Có thể thấy, sau cú lật thuyền xưa kia, ngay cả những bạn sinh ra từ biển cũng còn rén, luôn chọn cho mình chỗ an toàn nhất và phải bên cạnh một người để có thể ôm chặt khi thuyền chao đảo. Lấy ví dụ, giả sử phao chuối có n=7 vị trí ngồi với dãy biểu diễn độ an toàn của các vị trí là (7,2,5,1,4,6,3) và vị trí ưa thích của GSPVH là f=3. Khi đó, mọi người sẽ lựa chọn chỗ ngồi như sau:

• Trước hết, toàn bộ n vị trí trên phao chuối đều trống: _ _ _ _ _ _ _
• Đầu tiên, GSPVH (người thứ 11) ngồi vào vị trí ưa thích f=3: _ _ 1 _ _ _ _
• Bạn thứ 2 ngồi vào vị trí 4: _ _ 1 2 _ _ _
• Bạn thứ 3 ngồi vào vị trí 2: _ 3 1 2 _ _ _
• Bạn thứ 4 ngồi vào vị trí 5: _ 3 1 2 4 _ _
• Bạn thứ 5 ngồi vào vị trí 6: _ 3 1 2 4 5 _
• Bạn thứ 6 ngồi vào vị trí 7: _ 3 1 2 4 5 6
• Bạn thứ 7 ngồi vào vị trí 1: 7 3 1 2 4 5 6

Tuy nhiên, cuộc sống không ngừng biến đổi đi lên, và phao chuối cũng ngày càng được cải tiến. Gần đây, GSPVH phát hiện nhiều công trình khoa học đã ra đời nhằm nâng cấp độ an toàn của các vị trí ngồi trên phao chuối. Mỗi công trình nghiên cứu được biểu diễn bởi hai con số k và c (1≤k,c≤n) với ý nghĩa: vị trí ngồi thứ k được nâng cấp và giờ trở thành vị trí có độ an toàn thức c. Lưu ý rằng ở mọi thời điểm, sau mọi sự nâng cấp, độ an toàn của các vị trí ngồi luôn đôi một phân biệt. Cụ thể, giả sử p1​,p2​,…,pn​ là hoán vị biểu diễn độ an toàn của các vị trí ngồi trước sự nâng cấp, cách xác định hoán vị p1′​,p2′​,…,pn′​ biểu diễn độ an toàn của các vị trí ngồi sau sự nâng cấp như sau:

• Đặt o=pk​. Chú ý rằng, do vị trí ngồi thứ k được nâng cấp nên chắc chắn vị trí này có độ an toàn cao hơn trước. Vì vậy, dữ liệu vào luôn đảm bảo c<o.

•  cpk′​=c

• Với mọi vị trí i có 1≤i≤n và c≤pi​≤o−1, ta có ​pi'=pi​+1.
• Với mọi vị trí i có 1≤i≤n và 1≤pi​≤c−1, ta có pi'​=pi​.
• Với mọi vị trí i có  1≤i≤n và o+1≤pi​≤n, ta có pi′​=pi​.

Việc có quá nhiều cải tiến khoa học về phao chuối khiến cho GSPVH rất khó quản lý độ an toàn của các vị trí ngồi, vì vậy GSPVH muốn nhờ bạn viết chương trình xử lý qq sự kiện, mỗi sự kiện thuộc một trong hai dạng sau:

• U k c: Có công trình khoa học nâng cao độ an toàn của vị trí thứ k lên mức c (như định nghĩa ở trên)
• G xx: Cho biết với độ an toàn của các vị trí như ở thời điểm hiện tại, ai sẽ ngồi vào vị trí thứ x, biết rằng GSPVH cùng những học sinh đi cùng vẫn chọn chỗ ngồi theo chiến lược ở trên.

Các bạn hãy giúp GSPVH nhé.

Input

• Dòng đầu tiên chứa số nguyên θ là số thứ tự của subtask chứa test này.
• Dòng thứ hai chứa ba số nguyên n,q và f  (1≤f≤n≤6662,1≤q≤7772) lần lượt là số vị trí ngồi trên phao chuối, số thao tác cần được xử lý và vị trí ưa thích của GSPVH.
• Dòng thứ ba chứa nn số nguyên v1,v2,...,vn(1≤vi​≤n) là một hoán vị của các số nguyên từ 1 đến n biểu diễn độ an toàn của n vị trí ngồi ở thời điểm ban đầu.
• Trong qq dòng cuối cùng, mỗi dòng mô tả một thao tác thuộc một trong hai dạng sau:
  • U k c (1≤k,c≤n) mô tả một sự cải tiến độ an toàn. Dữ liệu vào đảm bảo nếu  p_{n}p1​,p2​,…,pn​ là hoán vị biểu diễn độ an toàn của n vị trí trước thao tác này, }c<pk​.
  • G x (1≤x≤n) yêu cầu tìm người sẽ ngồi vào vị trí thứ x.

Output

• Với mỗi thao tác dạng G x, in ra một số nguyên trên một dòng thể hiện kết quả.

Scoring

• Subtask 1 (3 điểm):n≤66^2 và q≤77^2.
• Subtask 2 (9 điểm): Có tối đa 6666 thao tác dạng U kk cc.
• Subtask 3 (13 điểm): Mọi thao tác dạng U kk cc đều xuất hiện trước mọi thao tác dạng G xx.
• Subtask 4 (13 điểm): Mọi thao tác dạng U kk cc đều thoả mãn c≤11.
• Subtask 5 (12 điểm): n≤222^2.
• Subtask 6 (10 điểm): Không có ràng buộc gì thêm.
• cx đc