AT_abc254_g [ABC254G] Elevators

有一座由 $N$ 栋 $10^9$ 层高的楼组成的大楼群。每栋楼编号为 $1$ 到 $N$。 任意两栋不同的楼在相同的楼层之间通过连廊相连，可以在 $1$ 分钟内完成楼间移动。 此外，有 $M$ 部电梯。第 $i$ 部电梯连接第 $A_i$ 栋楼的 $B_i$ 层到 $C_i$ 层。使用这部电梯时，对于所有满足 $B_i \leq x, y \leq C_i$ 的整数对 $(x, y)$，可以在 $|x-y|$ 分钟内从第 $A_i$ 栋楼的 $x$ 层移动到 $y$ 层。 请回答以下 $Q$ 个询问。 - 判断是否可以从第 $X_i$ 栋楼的 $Y_i$ 层移动到第 $Z_i$ 栋楼的 $W_i$ 层，如果可以，输出所需的最短时间；否则输出 $-1$。

输入通过标准输入按以下格式给出。 > $N$ $M$ $Q$ > $A_1$ $B_1$ $C_1$ > $A_2$ $B_2$ $C_2$ > $\vdots$ > $A_M$ $B_M$ $C_M$ > $\mathrm{query}_1$ > $\mathrm{query}_2$ > $\vdots$ > $\mathrm{query}_Q$ 每个询问的格式如下： > $X_i$ $Y_i$ $Z_i$ $W_i$

输出 $Q$ 行。第 $i$ 行对应第 $i$ 个询问，如果无法到达则输出 $-1$，否则输出最短移动时间。

## 数据范围 - $1 \leq N, M, Q \leq 2 \times 10^5$ - $1 \leq A_i \leq N$ - $1 \leq B_i < C_i \leq 10^9$ - $1 \leq X_i, Z_i \leq N$ - $1 \leq Y_i, W_i \leq 10^9$ - 所有输入均为整数。 ## 样例解释 1 对于第 $1$ 个询问，可以按如下方式在 $12$ 分钟内完成移动： - 使用第 $1$ 部电梯，从第 $1$ 栋楼的 $3$ 层移动到 $9$ 层，耗时 $6$ 分钟。 - 在第 $9$ 层通过连廊从第 $1$ 栋楼移动到第 $3$ 栋楼，耗时 $1$ 分钟。 - 使用第 $3$ 部电梯，从第 $3$ 栋楼的 $9$ 层移动到 $14$ 层，耗时 $5$ 分钟。 对于第 $3$ 个询问，无法完成移动，因此输出 $-1$。 由 ChatGPT 4.1 翻译