#889. PHOTO - Bức ảnh đẹp

Cho viên bi xếp thành hàng ngang, viên thứ có màu . 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 .

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:

• Dòng đầu chứa hai số ;
• Dòng thứ hai chứa số ;
• Dòng thứ ba chứa số ;
• dòng sau, mỗi dòng chứa thông tin một truy vấn.

Kết quả:

• Ứng với mỗi truy vấn, in kết quả trên một dòng. Nếu bức ảnh là đẹp thì ghi 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 .

Ví dụ:

Dữ liệu:

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

Kết quả:

0
1 1
0
1 1
0
1 2
0 
1 3

Ràng buộc:

• số test tương ứng với số điểm có ;
• số test tương ứng với số điểm có ;
• số test tương ứng với số điểm không có ràng buộc gì thêm.