시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 4 4 4 100.000%

문제

There are N antennas, numbered from 1 to N along a line. Each antenna is one kilometer distant from consecutive antennas. The height of the antenna i (1 ≤ i ≤ N) is Hi. The antenna i can send information to the antennas located between Ai kilometers and Bi kilometers, inclusive, from the antenna i. If and only if the antenna x and the antenna y (1 ≤ x < y ≤ N) can send information to each other, the pair of antennas is in communication, and the communication cost is equal to |Hx − Hy|.

Mr. K, the Prime Minister of JOI Republic, has received Q complaints about bad connection from the citizens. A study showed that, for the j-th complaint (1 ≤ j ≤ Q), something among the antennas Lj, Lj+1, . . . , Rj has troubles. You are assigned to find whether there exists a pair of antennas in communication among the antennas Lj, Lj+1, . . . , Rj, and if there does, you also have to find the maximum communication cost among such pairs.

Write a program which, given the information of antennas and complaints, determines whether there exists a pair of antennas in communication among the antennas Lj, Lj+1, . . . , Rj and calculates the maximum communication cost among such pairs if there exists such a pair.

입력

Read the following data from the standard input. All the values in the input are integers.

N
H1 A1 B1
.
.
.
HN AN BN
Q
L1 R1
.
.
.
LQ RQ

출력

Write Q lines to the standard output. The j-th line (1 ≤ j ≤ Q) should be −1 if there is no pair of antennas in communication among the antennas Lj, Lj+1, . . . , Rj, or the maximum communication cost among such pairs otherwise.

제한

  • 2 ≤ N ≤ 200 000.
  • 1 ≤ Hi ≤ 1 000 000 000 (1 ≤ i ≤ N).
  • 1 ≤ Ai ≤ Bi ≤ N − 1 (1 ≤ i ≤ N).
  • 1 ≤ Q ≤ 200 000.
  • 1 ≤ Lj < Rj ≤ N (1 ≤ j ≤ Q).

예제 입력 1

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
1
8
8
99

The antenna 1 and the antenna 2 are not in communication, so the answer to the 1st complaint is −1.

The pair of antennas in communication which has the maximum communication cost for the 2nd, 3rd, 4th and 5th complaint is (2, 3), (1, 3), (1, 3), and (4, 5), respectively.

예제 입력 2

20
260055884 2 15
737689751 5 5
575359903 1 15
341907415 14 14
162026576 9 19
55126745 10 19
95712405 11 14
416027186 8 13
370819848 11 14
629309664 4 13
822713895 5 15
390716905 13 17
577166133 8 19
195931195 10 17
377030463 14 17
968486685 11 19
963040581 4 10
566835557 1 12
586336111 6 16
385865831 8 9
1
1 20

예제 출력 2

806460109