#1303. RMQCHK - Kiểm tra RQM

Bờm viết một chương trình trả lời các truy vấn RMQ (range minimum query) trên dãy số đôi một phân biệt, trong đó dữ liệu được cho trong hai file: file chứa dãy số và file chứa truy vấn.

Bờm lỡ tay làm hỏng file chứa dãy số nên không kiểm tra được tính đúng dắn của kết quả. Vì vậy Bờm nhờ bạn xác định xem các trả lời của chương trình có là hợp lệ hay không.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên là kích thước dãy số và số truy vấn;
• dòng tiếp theo, dòng thứ ghi ba số nguyên chỉ truy vấn thứ thực hiện tìm được kết quả là .

Dữ liệu ra:

• Ghi ra duy nhất một số nguyên kết quả, số này bằng nếu các trả lời truy vấn là không mâu thuẫn, ngược lại số này là số hiệu truy vấn đầu tiên có kết quả mâu thuẫn với các truy vấn trước đó.

Ví dụ:

Dữ liệu vào:

20 4
1 10 7
5 19 7
3 12 8
11 15 12

Dữ liệu ra:

3

Giải thích: do các phần tử của dãy là đôi một phân biệt nên cho ta , điều này mâu thuẫn với .