提示: 欢迎访问OurACM平台。
Problem 2235 国王的出游

Accept: 49    Submit: 260
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

黑暗之王有一片棋盘般的疆土,这片疆土有2*10^9行,有2*10^9列。假设这块疆土的行从上到下编号1到2*10^9,它的列从左到右也编号1到2*10^9。我们可以把第i行第j列的方格记为坐标(i,j)。

但是这偌大棋盘只有被给的N个线状区域才是允许通行的。每个线状区域被三个参数描述,ri,ai,bi(ai<= bi)。ri代表给定线状区域的行编号,ai代表线状区域的起始列编号,bi代表末尾编号。

现在国王想要从一个给定坐标方格(x0,y0)通过最小移动步数到达终点坐标方格(x1,y1),而且只能通过上述给出的允许通行的线状区域。

国王移动一步只能发生在相邻的方格之间。此外,如果两个方格至少共享一个点我们便认为他们相邻。

Input

有多组数据(<=30),处理到文件尾(EOF)。

每组数据第一行包含四个整数,x0, y0, x1, y1(1 <= x0, y0, x1, y1 <= 2*10^9),分别代表国王的初始坐标和终点坐标。

第二行有一个整数N (1 <= N <= 10^5),代表有N条可通行的线状区域。

接下里会有N行,第i行包含三个整数,ri,ai, bi (1 <= ri, ai bi <= 2*10^9),含义看题面。

数据允许线状区域会有交叉或者嵌套。

数据保证国王的起点方格和终点方格都是可通行的,并且两个区域不相同。另外保证所有线状区域的的长度总和不超过10^5。

1 <= x0, y0, x1, y1, ri, ai, bi<= 2*10^9,1 <= N <= 10^5

Output

如果没有一条道路使得国王从起始区域到达终点区域,则输出 -1。

否则,则输出国王的从起始区域到达终点区域的最小步数。

Sample Input

5 7 6 11 3 5 3 8 6 7 11 5 2 5 1 1 2 10 2 1 1 3 2 6 10

Sample Output

4 -1

Source

福州大学第十三届程序设计竞赛

Submit  Back  Status  Discuss