Krastoboj là trò chơi hai người trên các dãy số nguyên dương. Ở một lượt, người chơi chọn một dãy hiện có và một giá trị \(x\) xuất hiện trong dãy, xóa mọi lần xuất hiện của \(x\); các đoạn còn lại tạo thành các dãy mới. Người không thể đi thua.

Ban đầu có một dãy con liên tiếp của dãy mẫu \(a\). Với mỗi truy vấn \([l,r]\), hãy cho biết người thắng khi Toni đi trước và cả hai chơi tối ưu.

Dữ liệu vào

Dòng đầu chứa \(n,q\) (\(1\le n,q\le10^5\)). Dòng hai chứa \(a_i\) (\(1\le a_i\le32\)). \(q\) dòng tiếp theo chứa \(l,r\) (\(1\le l\le r\le n\)).

Dữ liệu ra

Với mỗi truy vấn, in Toni hoặc Jakov trên một dòng.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(15\) điểm: \(n,q\le10\).
2. \(11\) điểm: \(n,q\le1000\) và \(a_i\le2\).
3. \(18\) điểm: \(n,q\le1000\).
4. \(14\) điểm: \(a_i\le2\).
5. \(23\) điểm: \(a_{l_i}=a_{r_i}\) với mọi truy vấn.
6. \(29\) điểm: không có ràng buộc thêm.

Ví dụ

6 4
1 3 2 3 1 2
1 1
2 3
2 4
1 3

Toni
Jakov
Toni
Toni

10 5
3 3 3 1 2 2 1 2 2 1
2 3
9 10
5 6
5 8
3 7

Toni
Jakov
Toni
Toni
Toni

Nguồn

COCI 2025/2026 - Vòng 1, bài Zagi.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.