Score : $600$ points

问题描述

存在一个由 $N$ 座 $10^9$ 层摩天大楼组成的综合建筑群。这些摩天大楼按编号从 $1$ 到 $N$ 编号，楼层则按编号从 $1$ 到 $10^9$ 编号。

从任何一座摩天大楼的任意一层楼出发，都可以通过空中连廊在一分钟内到达另一座任意摩天大楼的同一层楼。

另外，还有 $M$ 部电梯。第 $i$ 部电梯在摩天大楼 $A_i$ 的第 $B_i$ 层与第 $C_i$ 层之间运行。利用这部电梯，在满足 $B_i \le x,y \le C_i$ 条件下的每一对整数楼层 $x$ 和 $y$，可以在 $|x-y|$ 分钟内从摩天大楼 $A_i$ 的第 $x$ 层到达第 $y$ 层。

接下来需要回答 $Q$ 个查询。

• 确定是否可以从摩天大楼 $X_i$ 的第 $Y_i$ 层到达摩天大楼 $Z_i$ 的第 $W_i$ 层，并在可能的情况下找出到达那里所需的最短时间。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a complex composed of $N$ $10^9$-story skyscrapers. The skyscrapers are numbered $1$ to $N$, and the floors are numbered $1$ to $10^9$.

From any floor of any skyscraper, one can use a skybridge to get to the same floor of any other skyscraper in one minute.

Additionally, there are $M$ elevators. The $i$-th elevator runs between Floor $B_i$ and Floor $C_i$ of Skyscraper $A_i$. With this elevator, one can get from Floor $x$ to Floor $y$ of Skyscraper $A_i$ in $|x-y|$ minutes, for every pair of integers $x,y$ such that $B_i \le x,y \le C_i$.

Answer the following $Q$ queries.

• Determine whether it is possible to get from Floor $Y_i$ of Skyscraper $X_i$ to Floor $W_i$ of Skyscraper $Z_i$, and find the shortest time needed to get there if it is possible.

Constraints

• $1 \le N,M,Q \le 2 \times 10^5$
• $1 \le A_i \le N$
• $1 \le B_i < C_i \le 10^9$
• $1 \le X_i,Z_i \le N$
• $1 \le Y_i,W_i \le 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$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$

Each query is in the following format:

$X_i$ $Y_i$ $Z_i$ $W_i$

Output

Print $Q$ lines. The $i$-th line should contain -1 if, for $\mathrm{query}_i$, the destination is unreachable; otherwise, it should contain the minimum number of minutes needed to get there.

Sample Input 1

3 4 3
1 2 10
2 3 7
3 9 14
3 1 3
1 3 3 14
3 1 2 7
1 100 1 101

Sample Output 1

12
7
-1

For the $1$-st query, you can get to the destination in $12$ minutes as follows.

• Use Elevator $1$ to get from Floor $3$ to Floor $9$ of Skyscraper $1$, in $6$ minutes.
• Use the skybridge on Floor $9$ to get from Skyscraper $1$ to Skyscraper $3$, in $1$ minute.
• Use Elevator $3$ to get from Floor $9$ to Floor $14$ of Skyscraper $3$, in $5$ minutes.

For the $3$-rd query, the destination is unreachable, so -1 should be printed.

Sample Input 2

1 1 1
1 1 2
1 1 1 2

Sample Output 2

1

update @ 2024/3/10 10:50:35