Thành phố phát triển dựa trên hệ thống phủ sóng của các mạng , thành phố hiện có điểm phát mạng đánh số từ đến , khoảng cách giữa
điểm và là . Biết được rằng, điểm thứ khi phát thì chỉ phát được đến những điểm sao cho
hay nói cách khác, điểm chỉ phát được trong khoảng cách từ đến . Độ cao của điểm thứ là . điểm phát mạng và được xem là liên thông nếu điểm có thể phát mạng cho và ngược lại, chiều cao chênh lệch của điểm liên thông càng lớn thì độ nhiễu càng cao. Vì thế chủ tịch thành phố muốn tính độ chênh lệch chiều cao lớn nhất giữa các cặp liên thông trong đoạn bất kì. Cho truy vấn, mỗi truy vấn gồm số và yêu cầu bạn tìm số và () sao cho liên thông với nhau đồng thời đạt giá trị lớn nhất.
Input
Sample Input
Copy
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5
Sample Output
Copy
-1
1
8
8
99
SUBTASK
- số test có
- số test có
- số test còn lại không có ràng buộc gì thêm.
Bình luận