Dãy số

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$.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương $n$ $(1\le n\le 2·{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·{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.

Dữ liệu ra

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$.

Ràng buộc

• $1\le n,q\le 2·{10}^5$
• $1\le a_i\le {10}^9$, $1\le x_i\le y_i\le n$
• $1\le l\le r\le n$

Subtasks

• Subtask 1 ($20\%$ số điểm): $n,q\le 500$.
• Subtask 2 ($30\%$ số điểm): $n,q\le 2000$.
• Subtask 3 ($50\%$ số điểm): Không có giới hạn gì thêm.

Ví dụ