두 안테나

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$번 안테나 중 무언가가 이상이 있는것으로 밝혀졌다. 당신은, 이 안테나들중 서로 통신할 수 있는 안테나 쌍이 있는지, 만약 있다면 그 중 가장 통신 비용이 높은 쌍의 통신 비용은 얼마인지 알아보는 일을 맡았다.

안테나의 정보와 불만의 정보가 주어졌을 때, $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$번째 ($1 \le j \le Q$)줄은 $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$).