Thành phố Hoài Nhơn phát triển hệ thống phủ sóng mạng 5G. 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; chênh lệch chiều cao 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~, hãy tìm 2 số ~i~ và ~j~ (~l \le i < j \le r~) sao cho chúng 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 \times 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 \times 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à 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 1

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
1
8
8
99