Bài toán: Vòng Tròn Đổi Màu

Đề bài

Cho ~n~ ô vuông được xếp thành một vòng tròn, đánh số thứ tự từ ~1~ đến ~n~ theo chiều kim đồng hồ. Ô thứ ~n~ kề với ô thứ ~1~. Mỗi ô được tô bởi một trong ba màu, được mã hóa bằng các số nguyên ~0, 1~ và ~2~.

Một người chơi thực hiện một trò chơi di chuyển và đổi màu trên vòng tròn này như sau: Tại bước thứ ~i~ (~i \ge 1~), người chơi sẽ dẫm hai chân lên hai ô kề nhau:

• Bước ~1~: dẫm lên ô ~1~ và ô ~2~.
• Bước ~2~: dẫm lên ô ~2~ và ô ~3~.
• ...
• Bước ~n~: dẫm lên ô ~n~ và ô ~1~.
• Bước ~n+1~: quay lại dẫm lên ô ~1~ và ô ~2~.
• Quy luật lặp lại tương tự cho các bước tiếp theo.

Quy tắc đổi màu: Khi dẫm lên 2 ô:

• Nếu 2 ô mang khác màu, người chơi sẽ sử dụng phép thuật để biến cả 2 ô đó thành màu thứ ba còn lại (ví dụ: đang là ~0~ và ~1~ thì biến thành ~2~; đang là ~0~ và ~2~ thì biến thành ~1~).
• Nếu 2 ô mang cùng màu, người chơi giữ nguyên màu của cả 2 ô.

Yêu cầu: Cho biết mảng màu ban đầu của ~n~ ô. Hãy xác định màu sắc của ô thứ ~t~ sau khi người chơi thực hiện xong đúng ~k~ bước.

Dữ liệu vào (Input)

• Dòng đầu tiên chứa ba số nguyên dương ~n, k, t~ (~3 \le n \le 100~; ~1 \le k \le 10^{18}~; ~1 \le t \le n~) — lần lượt là số lượng ô, số bước di chuyển và vị trí ô cần truy vấn.
• Dòng thứ hai chứa ~n~ số nguyên ~x_1, x_2, \dots, x_n~ (~x_i \in \{0, 1, 2\}~) — màu sắc ban đầu của các ô.

Dữ liệu ra (Output)

• In ra một số nguyên duy nhất (~0, 1~ hoặc ~2~) là màu sắc của ô thứ ~t~ sau khi thực hiện xong ~k~ bước. Nếu sau ~k~ bước mà người chơi chưa từng dẫm lên ô ~t~ lần nào, in ra màu sắc ban đầu của ô đó.

Giới hạn (Subtasks)

• Subtask 1 (40% số điểm): ~n \le 100~; ~k \le 10^5~.
• Subtask 2 (60% số điểm): ~n \le 100~; ~k \le 10^{18}~.

Ví dụ 1

Input:

4 4 1
0 1 1 2

Output:

0

Giải thích Ví dụ 1:

• Ban đầu: [0, 1, 1, 2].
• Bước 1 (dẫm ô 1, 2): màu ~0~ và ~1~ biến thành ~2~. Vòng tròn thành [2, 2, 1, 2].
• Bước 2 (dẫm ô 2, 3): màu ~2~ và ~1~ biến thành ~0~. Vòng tròn thành [2, 0, 0, 2].
• Bước 3 (dẫm ô 3, 4): màu ~0~ và ~2~ biến thành ~1~. Vòng tròn thành [2, 0, 1, 1].
• Bước 4 (dẫm ô 4, 1): màu ~1~ (ô 4) và ~2~ (ô 1) biến thành ~0~. Vòng tròn thành [0, 0, 1, 0]. Sau ~4~ bước, ô thứ ~1~ mang màu ~0~.

Ví dụ 2

Input:

3 100 2
0 1 2

Output:

2

Giải thích Ví dụ 2:

• Bạn có thể viết nháp để thấy rằng sau 1 vòng (3 bước), vòng tròn trở thành [2, 2, 2].
• Vì sau đó tất cả các ô đều cùng màu, nên dù có đi thêm bao nhiêu bước, quy tắc "cùng màu thì giữ nguyên" sẽ khiến vòng tròn không bao giờ đổi màu nữa.
• Do đó ở bước 100, ô số 2 vẫn giữ màu ~2~.