The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Codeforces Round 149 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dfs and similar

graphs

hashing

shortest paths

*1800

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. King's Path

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe black king is standing on a chess field consisting of 10^{9} rows and 10^{9} columns. We will consider the rows of the field numbered with integers from 1 to 10^{9} from top to bottom. The columns are similarly numbered with integers from 1 to 10^{9} from left to right. We will denote a cell of the field that is located in the *i*-th row and *j*-th column as (*i*, *j*).

You know that some squares of the given chess field are allowed. All allowed cells of the chess field are given as *n* segments. Each segment is described by three integers *r*_{i}, *a*_{i}, *b*_{i} (*a*_{i} ≤ *b*_{i}), denoting that cells in columns from number *a*_{i} to number *b*_{i} inclusive in the *r*_{i}-th row are allowed.

Your task is to find the minimum number of moves the king needs to get from square (*x*_{0}, *y*_{0}) to square (*x*_{1}, *y*_{1}), provided that he only moves along the allowed cells. In other words, the king can be located only on allowed cells on his way.

Let us remind you that a chess king can move to any of the neighboring cells in one move. Two cells of a chess field are considered neighboring if they share at least one point.

Input

The first line contains four space-separated integers *x*_{0}, *y*_{0}, *x*_{1}, *y*_{1} (1 ≤ *x*_{0}, *y*_{0}, *x*_{1}, *y*_{1} ≤ 10^{9}), denoting the initial and the final positions of the king.

The second line contains a single integer *n* (1 ≤ *n* ≤ 10^{5}), denoting the number of segments of allowed cells. Next *n* lines contain the descriptions of these segments. The *i*-th line contains three space-separated integers *r*_{i}, *a*_{i}, *b*_{i} (1 ≤ *r*_{i}, *a*_{i}, *b*_{i} ≤ 10^{9}, *a*_{i} ≤ *b*_{i}), denoting that cells in columns from number *a*_{i} to number *b*_{i} inclusive in the *r*_{i}-th row are allowed. Note that the segments of the allowed cells can intersect and embed arbitrarily.

It is guaranteed that the king's initial and final position are allowed cells. It is guaranteed that the king's initial and the final positions do not coincide. It is guaranteed that the total length of all given segments doesn't exceed 10^{5}.

Output

If there is no path between the initial and final position along allowed cells, print -1.

Otherwise print a single integer — the minimum number of moves the king needs to get from the initial position to the final one.

Examples

Input

5 7 6 11

3

5 3 8

6 7 11

5 2 5

Output

4

Input

3 4 3 10

3

3 1 4

4 5 9

3 10 10

Output

6

Input

1 1 2 10

2

1 1 3

2 6 10

Output

-1

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/04/2023 09:16:01 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|