두 안테나

1번부터 $N$번까지 번호가 붙은 $N$개의 안테나가 일렬로 놓여 있다. 인접한 안테나끼리는 1km 떨어져 있다. $i$번 ($1 \le i \le N$) 안테나의 높이는 $H_i$이다. $i$번 안테나는 자신으로부터 $A_i$km 이상 $B_i$km 이하 떨어진 안테나에게만 정보를 보낼 수 있다. $x$번 안테나와 $y$번 안테나가 ($1 \le x < y \le N$) 서로 정보를 주고받을 수 있으면 이 둘은 통신할 수 있고, 통신 비용은 $|H_x - H_y|$이다.

JOI 공화국의 수상 K씨는 시민들로부터 연결 상태에 관한 불만 $Q$개를 들었다. 조사 결과 $j$번째 ($1 \le j \le Q$) 불만은 $L_j, L_j+1, \cdots, R_j$번 안테나 중 하나 이상에 이상이 있는 것으로 밝혀졌다. 이 안테나들 중에 서로 통신할 수 있는 쌍이 있는지, 있다면 그 중 통신 비용이 가장 높은 쌍의 비용이 얼마인지 구하라.

입력은 다음 형식으로 주어진다. 모든 값은 정수이다.

$N$

$H_1$ $A_1$ $B_1$

$\vdots$

$H_N$ $A_N$ $B_N$

$Q$

$L_1$ $R_1$

$\vdots$

$L_Q$ $R_Q$

표준 출력으로 $Q$개의 줄을 출력한다. $j$번째 줄에는 $L_j, L_j+1, \cdots, R_j$번 안테나 중 서로 통신할 수 있는 쌍이 없으면 -1을, 있으면 통신 비용의 최댓값을 출력한다.

• $2 \le N \le 200\,000$.
• $0 \le H_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le A_i \le B_i \le N-1$ ($1 \le i \le N$).
• $1 \le Q \le 200\,000$.
• $1 \le L_j < R_j \le N$ ($1 \le j \le Q$).