Có \(N\) ăng-ten, đánh số từ \(1\) đến \(N\), nằm trên một đường thẳng theo thứ tự đó. Khoảng cách giữa hai ăng-ten liên tiếp là \(1\) km. Ăng-ten \(i\) có độ cao \(H_i\) và có thể gửi thông tin đến những ăng-ten cách nó từ \(A_i\) đến \(B_i\) km, kể cả hai đầu mút.

Hai ăng-ten \(x,y\) với \(1\le x<y\le N\) liên lạc được với nhau khi và chỉ khi cả hai đều gửi thông tin được cho nhau. Chi phí liên lạc của cặp đó là \(|H_x-H_y|\).

Thủ tướng K của nước JOI nhận được \(Q\) phản ánh về kết nối kém. Với phản ánh thứ \(j\), sự cố nằm trong các ăng-ten \(L_j,L_j+1,\ldots,R_j\). Hãy xác định có cặp ăng-ten nào liên lạc được với nhau trong đoạn đó hay không; nếu có, tìm chi phí liên lạc lớn nhất của một cặp như vậy.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

N
H_1 A_1 B_1
...
H_N A_N B_N
Q
L_1 R_1
...
L_Q R_Q

Tất cả dữ liệu vào là số nguyên.

Dữ liệu ra

Ghi \(Q\) dòng. Dòng thứ \(j\) ghi -1 nếu không có cặp ăng-ten nào liên lạc được với nhau trong đoạn \([L_j,R_j]\); ngược lại, ghi chi phí liên lạc lớn nhất của một cặp trong đoạn đó.

Ràng buộc

• \(2\le N\le200\,000\).
• \(1\le H_i\le10^9\) với \(1\le i\le N\).
• \(1\le A_i\le B_i\le N-1\) với \(1\le i\le N\).
• \(1\le Q\le200\,000\).
• \(1\le L_j<R_j\le N\) với \(1\le j\le Q\).

Phân nhóm

1. (2 điểm) \(N\le300\) và \(Q\le300\).
2. (11 điểm) \(N\le2000\).
3. (22 điểm) \(Q=1\), \(L_1=1\), \(R_1=N\).
4. (65 điểm) Không có ràng buộc bổ sung.

Ví dụ

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

-1
1
8
8
99

20
260055884 2 15
737689751 5 5
575359903 1 15
341907415 14 14
162026576 9 19
55126745 10 19
95712405 11 14
416027186 8 13
370819848 11 14
629309664 4 13
822713895 5 15
390716905 13 17
577166133 8 19
195931195 10 17
377030463 14 17
968486685 11 19
963040581 4 10
566835557 1 12
586336111 6 16
385865831 8 9
1
1 20

806460109

Nguồn

JOI 2018/2019 Spring Training Camp, ngày 2. Đề gốc tiếng Anh, do Japanese Committee for the International Olympiad in Informatics công bố. Bản dịch tiếng Việt theo CC BY-SA 4.0.