Ăng-ten

Có \(N\) ăng-ten được đánh số từ \(1\) đến \(N\) và được đặt thẳng hàng trên một trục, mỗi cái cách nhau đúng \(1\) km. Ăng-ten thứ \(i\) có chiều cao là \(H_i\) và có thể truyền tín hiệu đến các ăng-ten nằm trong đoạn từ \(A_i\) đến \(B_i\) (tính theo khoảng cách từ vị trí \(i\)).

Cụ thể hơn, ăng-ten \(x\) và \(y\) \((1 \le x < y \le N)\) có thể truyền thông tin cho nhau nếu và chỉ nếu:

• \(x\) nằm trong đoạn mà \(y\) có thể truyền tới, và

• \(y\) nằm trong đoạn mà \(x\) có thể truyền tới.

Khi đó, hai ăng-ten được gọi là có thể liên lạc được, và chi phí liên lạc giữa hai ăng-ten này được tính là \(|H_x - H_y|\).

Thủ tướng K nhận được \(Q\) khiếu nại từ người dân về việc liên lạc kém. Mỗi khiếu nại liên quan đến một đoạn ăng-ten liên tiếp từ \(L_j\) đến \(R_j\). Với mỗi khiếu nại, hãy xác định xem có cặp ăng-ten nào trong đoạn đó có thể liên lạc được không. Nếu có, hãy in ra chi phí liên lạc lớn nhất giữa các cặp như vậy. Nếu không có cặp nào thỏa mãn, in ra \(-1\).

\InputFile

• Dòng đầu chứa số nguyên \(N\) (\(2 \le N \le 200\,000\)).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(H_i\), \(A_i\), \(B_i\) (\(1 \le H_i \le 10^9\), \(1 \le A_i \le B_i \le N - 1\)).
• Dòng tiếp theo chứa số nguyên \(Q\) (\(1 \le Q \le 200\,000\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L_j, R_j\) (\(1 \le L_j < R_j \le N\)).

\OutputFile

In ra \(Q\) dòng. Dòng thứ \(j\) in ra \(-1\) nếu không tồn tại cặp ăng-ten nào trong đoạn \([L_j, R_j]\) có thể liên lạc với nhau. Ngược lại, in ra chi phí liên lạc lớn nhất giữa các cặp liên lạc được.

\Scoring

• Subtask 1 (10%): \(N, Q \le 300\)
• Subtask 2 (25%): \(N \le 2000\)
• Subtask 3 (25%): \(Q = 1\), \(L_1 = 1\), \(R_1 = N\)
• Subtask 4 (40%): Không có ràng buộc bổ sung

Example

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