Cho 𝑛 viên vi xếp thành hàng ngang, viên thứ 𝑖 có màu 𝑎𝑖 (1 ≤ 𝑎_𝑖 ≤ 𝐶). Một bức ảnh đẹp là một đoạn con liên tiếp các viên bi sao cho trong đó có nhiều hơn một nửa trong số đó có cùng màu.

Cho 𝑄 truy vấn, mỗi truy vấn cho hai số nguyên 𝑖,𝑗 (1 ≤ 𝑖 ≤ 𝑗 ≤ 𝑛).

Yêu cầu: Với mỗi truy vấn, kiểm tra xem bức ảnh chụp đoạn [𝑖,𝑗] có đẹp không? Màu nào xuất hiện nhiều hơn một nửa trong số các viên bi trong đoạn đó.

Dữ liệu vào:

- Dòng đầu chứa hai số 𝑛, 𝐶 (3 ≤ 𝑛 ≤ 300 000, 1 ≤ 𝐶 ≤ 10 000)
- Dòng tiếp chứa 𝑛 số 𝑎1, 𝑎2, … , 𝑎𝑛 (1 ≤ 𝑎𝑖 ≤ 𝐶)
- Dòng tiếp chứa số 𝑄(1 ≤ 𝑄 ≤ 10 000)
- 𝑄 dòng sau, mỗi dòng chứa thông tin một truy vấn.

Kết quả:

- Tương ứng với mỗi truy vấn, in kết quả trên một hàng. Nếu bức ảnh là đẹp thì ghi “1 𝑥" với 𝑥 là màu xuất hiện quá một nửa trong số các viên bi. Ngược lại, in “0”.

Các ràng buộc:

Sub 1: 20% các test đầu tiên có 𝑛, 𝑄 ≤ 1000
Sub 2: 20 % số test tiếp theo có 𝑛 ≤ 300 000,𝑄 ≤ 10 000, 1 ≤ 𝐶 ≤ 30
Sub 3: 60% số test còn lại không có ràng buộc gì thêm.