Cho dãy ~a~ gồm ~n~ số nguyên dương. Các số trong dãy được đánh số thứ tự từ ~1~ đến ~n~. Mỗi phần tử ~i~ ~(1 \le i \le n)~ có giá trị trái ~x_i~ và giá trị phải là ~y_i~. Cho ~q~ truy vấn, mỗi truy vấn gồm hai số nguyên ~l, r~ ~(1 \le l \le r \le n)~, yêu cầu tìm hai phần tử ~i, j~ thỏa mãn đồng thời các điều kiện sau:

• ~l \le i < j \le r~;

• ~x_i \le |i-j| \le y_i~;

• ~x_j \le |j-i| \le y_j~;

• ~|a_i-a_j|~ đạt giá trị lớn nhất.

Yêu cầu: Với mỗi truy vấn, in ra giá trị ~|a_i-a_j|~ lớn nhất có thể. Nếu không có hai phần tử nào thỏa mãn thì in ra ~-1~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 2 \cdot 10^5)~ là số phần tử của dãy;

• ~n~ dòng tiếp theo, dòng thứ ~i~ ~(1 \le i \le n)~ chứa ba số nguyên ~a_i, x_i, y_i~ ~(1 \le a_i \le 10^9, 1 \le x_i \le y_i \le n)~ lần lượt là giá trị, giá trị trái, giá trị phải của số thứ ~i~;

• Dòng tiếp theo chứa số nguyên ~q~ ~(1 \le q \le 2 \cdot 10^5)~ là số truy vấn;

• ~q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~l, r~ mô tả một truy vấn.

Output

Gồm ~q~ dòng. Dòng thứ ~i~ ~(1 \le i \le q)~ ghi một số nguyên duy nhất là kết quả tìm được cho truy vấn thứ ~i~.

Scoring

Sample Input 1

5
8 3 3
2 1 1
4 1 2
3 1 1
70 1 2
5
3 5
2 4
1 5
3 4
1 4

Sample Output 1

67
2
67
1
2