题目描述

有 $N$ 个天线，沿直线从 $1$ 到 $N$ 编号。每两个相邻天线之间的距离为 1 千米。天线 $i$（$1 \le i \le N$）的高度为 $H_i$。天线 $i$ 可以向距离其 $A_i$ 千米至 $B_i$ 千米（含端点）范围内的天线发送信息。当且仅当天线 $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, \ldots, R_j$ 中的某些天线存在故障。你的任务是判断在天线 $L_j, L_j + 1, \ldots, R_j$ 中是否存在一对处于通信状态的天线；若存在，还需找出所有此类天线对中的最大通信成本。

编写一个程序，在给定天线信息和投诉信息后，判断在天线 $L_j, L_j + 1, \ldots, 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$）应为 $-1$，若在天线 $L_j, L_j + 1, \ldots, R_j$ 中不存在任何处于通信状态的天线对；否则，输出所有此类天线对中的最大通信成本。

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

提示

样例 1 解释

天线 1 与天线 2 之间无法通信，因此第 1 项投诉的答案为 $-1$。

对于第 2、3、4、5 项投诉，通信成本最大的通信天线对分别为 $(2, 3)$、$(1, 3)$、$(1, 3)$ 和 $(4, 5)$。

数据范围

• $2 \le N \le 200\,000$。
• $1 \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$）。

子任务

1. （2 分）$N \le 300$，$Q \le 300$。
2. （11 分）$N \le 2000$。
3. （22 分）$Q = 1$，$L_1 = 1$，$R_1 = N$。
4. （65 分）无额外约束。

翻译由 Qwen3-235B 完成