← 返回题目列表

Codeforces · 242/C

C. 国王之路

中文机器翻译题面 查看原题

黑王站在由109行109列组成的棋场上。我们将考虑从上到下用 1 到 109 的整数编号的字段行。类似地,这些列从左到右使用 1 到 109 的整数进行编号。我们将位于第 i 行第 j 列的字段单元格表示为 (i, j)。

您知道给定的国际象棋场上的某些方格是允许的。国际象棋场中所有允许的单元都以 n 段的形式给出。每个段由三个整数ri、ai、bi(ai≤bi)描述,表示第ri行中从编号ai到编号bi的列中的单元格是允许的。

你的任务是找到国王从方格 (x0, y0) 到方格 (x1, y1) 所需的最少移动次数,前提是他只沿着允许的方格移动。换句话说,国王只能在途中找到允许的单元格。

让我们提醒您,国际象棋王可以一步移动到任何相邻的方格。如果棋场中的两个方格至少共享一个点,则它们被视为相邻方格。

输入

第一行包含四个空格分隔的整数 x0, y0, x1, y1 (1 ≤ x0, y0, x1, y1 ≤ 109),表示国王的初始和最终位置。

第二行包含一个整数n (1 ≤ n ≤ 105),表示允许的单元格的段数。接下来的 n 行包含这些段的描述。第 i 行包含三个空格分隔的整数 ri, ai, bi (1 ≤ ri, ai, bi ≤ 109, ai ≤ bi),表示第 ri 行中从编号 ai 到编号 bi 的列中允许存在单元格。请注意,允许的单元格的片段可以任意交叉和嵌入。

保证国王的初始位置和最终位置都是允许的单元格。保证国王的初始位置和最终位置不重合。保证所有给定段的总长度不超过105。

输出

如果沿允许的单元格的初始位置和最终位置之间没有路径,则打印 -1。

否则打印一个整数——国王从初始位置到最终位置所需的最小移动次数。

示例

输入 #1

5 7 6 11
3
5 3 8
6 7 11
5 2 5

输出 #1

4

输入 #2

3 4 3 10
3
3 1 4
4 5 9
3 10 10

输出 #2

6

输入 #3

1 1 2 10
2
1 1 3
2 6 10

输出 #3

-1