分数: 600 点
问题陈述
有一个复杂的组成 N 10^9- 故事摩天大楼。摩天大楼已被编号 1 to N,并且楼层已编号 1 to 10^9.
从任何摩天大楼的任何楼层,人们可以使用天桥在一分钟内到达任何其他摩天大楼的同一楼层。
此外,还有 M 电梯。的 i-th 电梯在楼层之间运行 B_i 和地板 摩天大楼的 C_i 摩天大楼 A_i。有了这部电梯,人们可以从 1 楼到达 x 到楼层 y 摩天大楼 A_i in |x-y| 分钟,对于每对整数 x,y 这样 B_i \le x,y \le C_i.
回答以下问题 Q 查询。
- 判断是否可以从Floor获取 Y_i 摩天大楼 X_i 到楼层 W_i 摩天大楼 Z_i,如果可能的话,找出到达那里所需的最短时间。
约束
- 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
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
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- 第行应包含 -1 如果,对于 \mathrm{query}_i,目的地不可达;否则,它应该包含到达那里所需的最少分钟数。
样本输入 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
示例输出 1
12 7 -1
对于 1-st查询,可以到达目的地 12 分钟如下。
- 使用电梯 1 从楼层获取 3 到楼层 9 摩天大楼 1,在 6 分钟。
- 使用楼层的天桥 9 从摩天大楼获取 1 前往摩天大楼 3,在 1 分钟。
- 使用电梯 3 从楼层获取 9 到楼层 14 摩天大楼 3,在 5 分钟。
对于 3-rd查询,目的地不可达,所以
应打印 -1 。
示例输入 2
1 1 1 1 1 2 1 1 1 2
示例输出 2
1