3033 「JOISC 2019 Day2」两个天线

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

有 $N$ 个天线排成一行，编号分别为 $1$ 到 $N$，相邻两个天线之间的距离都是 $1$。天线 $i$ 的高度为 $H_i$。天线 $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$ 和天线 $2$ 无法互相发消息，因此第一个询问答案为 -1。

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

这组样例满足子任务 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). $