Điệu valse
Đề bài
Mô tả
Là những vũ công xuất sắc, Katharina và bạn được mời mở màn điệu valse trong buổi dạ hội thường niên của Cộng đồng những người vụng về khét tiếng. Sau nhiều giờ luyện tập, cả hai đều tự tin vào kỹ năng của mình. Tuy nhiên, đúng như tên gọi, các vũ công khác có thể vụng về và nhầm bạn nhảy của người khác là của mình, nhất là trên một sàn nhảy hỗn loạn.
Năm nay, điệu valse mở màn được biểu diễn như sau: đầu tiên, tất cả vũ công đứng thành một hàng. Mỗi vũ công được phát một số hiệu (ID) để khán giả có thể theo dõi.
Sau đó, tại một số thời điểm, các vũ công ở vị trí từ đến thực hiện một điệu nhảy vòng bước. Nghĩa là nếu trước điệu nhảy, ID của vũ công theo thứ tự là mảng , thì sau điệu nhảy ID của họ trở thành
Khi mọi người cùng nhảy, bạn không muốn mất dấu người bạn nhảy quý giá của mình (nếu không, cô ấy sẽ rất giận bạn sau đó). Nhưng có ba vấn đề:
- Bạn vụng về, nên không thể theo dõi cô ấy trong lúc nhảy;
- Các vũ công khác cũng vụng về, nên dù trong mắt khán giả các ID có vẻ nhất quán, một vũ công có thể lại mang ID của người khác (đó là lý do cần có ID ngay từ đầu). Vì vậy, ngay cả ID của Katharina cũng có thể thay đổi.
- Ban tổ chức cũng vụng về, nên có thể có nhiều vũ công cùng một ID.
Biết vậy, thỉnh thoảng Katharina sẽ yêu cầu bạn nhận ra cô ấy. Cô ấy đưa cho bạn ba số , và , nghĩa là ID của cô ấy là số nhỏ thứ trong các ID của các vũ công ở vị trí từ đến trong hàng. Nói cách khác, nếu ID của vũ công là mảng , thì ID của cô ấy là số nhỏ thứ trong các số .
Dữ liệu vào
- Dòng đầu tiên gồm hai số nguyên và : số vũ công và số thao tác.
- Dòng thứ hai gồm số nguyên : ID ban đầu của các vũ công theo thứ tự trong hàng.
- dòng tiếp theo, dòng thứ gồm bốn số nguyên , , , . Giả sử trước thao tác này, ID của các vũ công theo thứ tự là .
- Nếu : các vũ công ở vị trí từ đến thực hiện điệu nhảy vòng bước, tức là sau đó ID của các vũ công là .
- Nếu : Katharina muốn bạn nhận ra cô ấy; ID của cô ấy là số nhỏ thứ trong .
Dữ liệu ra
Với mỗi thao tác loại , in ra ID của Katharina trên một dòng.
Ràng buộc
- , ,
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 10 10 10 5 7 5 1 9 8 1 10 1 1 6 10 1 2 1 4 2 2 3 7 3 1 9 10 1 2 5 8 2 2 2 4 1 1 4 10 4 2 6 8 1 1 1 10 9 2 1 3 1 |
5 5 1 5 1 5 |
Sau thao tác đầu tiên, mảng là . Số nhỏ thứ trong là . |
| 5 5 3 1 2 1 3 2 1 5 3 1 1 5 2 2 1 2 2 1 2 4 1 2 3 5 1 |
2 3 2 |
Ví dụ bổ sung. Sau thao tác thứ hai mảng là ; sau thao tác thứ tư là . |
Bình luận