题目描述

题目译自 JOISC 2019 Day2 T1「ふたつのアンテナ / Two Antennas」

有 $N$ 个天线排成一行，编号分别为 $1$ 到 $N$，相邻两个天线之间的距离都是 $1$。天线 $i$ 的高度为 $Hi$。天线 $i$ 可以向天线 $j$ 发送信息，当且仅当他们之间的距离 $D{i,j} \in [A_i, B_i]$。如果一对天线 $i$ 和 $j$ 可以互相发消息，那么我们定义他们之间的通信成本为 $\lvert H_i - H_j \rvert$。

JOI 共和国总理 K 先生收到了 $Q$ 件通信故障的投诉，对于第 $j$ 件投诉，你需要确定天线 $L_j, L_j+1, \ldots , R_j​$ 中是否存在一对天线可以互相发消息，如果存在，输出最大的通信成本。

输入格式

从标准输入中读取数据。

第一行一个整数 $N$。

接下来 $N$ 行，第 $i$ 行三个整数 $H_i, A_i, B_i$ 。

接下来一行一个整数 $Q$。

接下来 $Q$ 行，第 $j$ 行两个整数 $L_j, R_j$。

输出格式

输出数据到标准输出中。

输出 $Q$ 行，第 $j$ 行一个整数，表示第 $j$ 件投诉的最大通信成本，如果不存在可以互相发消息的天线，输出 -1。

样例 1

input

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

output

-1
1
8
8
99

天线 $1$ 和天线 $2$ 无法互相发消息，因此第一个询问答案为 -1。

对于第 $2, 3, 4, 5$ 个询问，能产生最大通信成本的天线对分别为 $(2, 3), (1, 3), (1,3), (4, 5)$。

样例 2

input

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

output

806460109

这组样例满足子任务 3 的限制。

数据范围与提示

对于所有输入数据，有
$ 2 \le N \le 200 000, \ 1 \le H_i \le 10^9 (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 \le R_j \le N (1 \le j \le Q). $