Thành phố ~T~ phát triển dựa trên hệ thống phủ sóng của các mạng ~4G~, thành phố hiện có ~n~ điểm phát mạng đánh số từ ~1~ đến ~n~, khoảng cách giữa ~2~ điểm ~i~ và ~j~ là ~|i - j|~. Biết được rằng, điểm thứ ~i~ khi phát thì chỉ phát được đến những điểm ~j~ sao cho ~A_i \le |i - j| \le B_i~ hay nói cách khác, điểm ~i~ chỉ phát được trong khoảng cách từ ~A_i~ đến ~B_i~. Độ cao của điểm thứ ~i~ là ~H_i~. ~2~ điểm phát mạng ~i~ và ~j~ được xem là liên thông nếu điểm ~i~ có thể phát mạng cho ~j~ và ngược lại, chiều cao chênh lệch của ~2~ đ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 ~1~ đoạn bất kì. Cho ~q~ truy vấn, mỗi truy vấn gồm ~2~ số ~l~ và ~r~ yêu cầu bạn tìm ~2~ số ~i~ và ~j~ (~l \le i < j \le r~) sao cho liên thông với nhau đồng thời ~|H_i - H_j|~ đạt giá trị lớn nhất.

Input

• Dòng đầu tiên ghi số ~n~ ~(1 \le n \le 2 * 10^5)~;
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~H_i~ ~A_i~ ~B_i~ (~1 \le H_i \le 10^9~ ~1 \le A_i \le B_i \le n~)
• Dòng tiếp theo là số ~q~ biểu thị số truy vấn (~1 \le q \le 2 * 10^5~).
• ~q~ dòng tiếp theo, dòng thứ ~i~ là các số ~l_i~ và ~r_i~ biểu diễn truy vấn thứ ~i~ (~1 \le l_i \le r_i \le n~).

• Output

• Gồm ~q~ dòng, dòng thứ ~i~ là cao chênh lệch lớn nhất giữa ~1~ cặp liên thông trong đoạn từ ~l_i~ đến ~r_i~ (nếu không tồn tại thì in ra ~-1~).

Sample Input

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

-1
1
8
8
99

SUBTASK

• ~50%~ số test có ~1 \le n, q \le 300~
• ~30%~ số test có ~1 \le n, q \le 2000~
• ~20%~ số test còn lại không có ràng buộc gì thêm.