两个天线

题号：NC53353
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

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

有N个天线排成一行，编号分别为1到N，相邻两个天线之间的距离都是1。天线i的高度为 $H_i$ 。天线i可以向天线j发送信息，当且仅当他们之间的距离 $L_{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行三个整数。
接下来一行一个整数Q。
接下来Q行，第j行两个整数。

输出描述:

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

示例1

输入

复制

输出

复制

说明

天线1和天线2无法互相发消息，因此第一个询问答案为-1。
对于第2,3,4,5个询问，能产生最大通信成本的天线对分别为(2,3),(1,3),(1,3),(4,5)。

示例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

输出

复制

806460109

备注:

对于所有输入数据，有

CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/3033