Problem Description

Peterland is structured like a grid, consisting of $N \times N$ sections. The section at the $ i $ $(1 \leq i \leq N)$th position from the west and the $ j $ $(1 \leq j \leq N)$th position from the north is represented as $ (i, j) $. Also, for any section, a section adjacent to it in one of the four cardinal directions (east, west, north, south) is called a neighboring section.

Pitaro, a high school student, is a very ordinary Peterrabbit living in Peterland. Or perhaps it would be more accurate to say he was. As a result of his repeated attempts to improve his chronic tardiness, Pitaro has gained the ability to warp. Normally, it takes Pitaro $ 1 $ byo to walk from one section to a neighboring section. However, using this warp ability, Pitaro can move to a neighboring section in $ 0 $ byo.

However, Pitaro uses solar energy to warp, so he cannot warp anywhere or in any direction. $ M $ pieces of information regarding the well-lit areas where Pitaro can warp are given. The $ k $th information $(1 \leq k \leq M)$ provides integers $ T_k, A_k, B_k, C_k, D_k $, which mean the following:

• When $ T_k = 1 $, for $A_k \leq i \leq B_k$ and $C_k \leq j \leq D_k - 1$, Pitaro can warp bidirectionally between $ (i, j) $ and $ (i, j + 1) $ as many times as he likes.
• When $ T_k = 2 $, for $A_k \leq i \leq B_k - 1$ and $C_k \leq j \leq D_k$, Pitaro can warp bidirectionally between $ (i, j) $ and $ (i + 1, j) $ as many times as he likes.

Pitaro is likely to be late for school again because he stayed up late. Pitaro's home is at $ (P, Q) $ and his school is at $ (R, S) $. Pitaro wants to know the minimum time it takes to get from home to school.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ P $ $ Q $ $ R $ $ S $ $ T_1 $ $ A_1 $ $ B_1 $ $ C_1 $ $ D_1 $ $\vdots$ $ T_M $ $ A_M $ $ B_M $ $ C_M $ $ D_M $

Output Format

Output the minimum time (in byo) it takes for Pitaro to get from home to school in one line to the standard output.

Sample Input and Output

Sample Input #1

8 9
2 1 3 7
2 3 8 8 8
2 1 3 1 2
2 2 5 3 4
2 5 7 7 7
1 6 8 3 7
1 1 4 7 8
1 1 1 2 4
2 3 6 4 5
2 6 7 1 1

Sample Output #1

3

Sample Input #2

10 6
1 1 1 9
1 1 1 1 2
1 1 1 7 10
1 1 1 3 5
1 1 1 4 6
1 1 1 1 2
1 1 1 8 10

Sample Output #2

2

Sample Input #3

12 0
1 3 1 11

Sample Output #3

8

Notes/Hints

Constraints

• All input values are integers.
• $1 \leq N \leq 1,000,000,000$.
• $0 \leq M \leq 1,000$.
• $1 \leq P, Q, R, S \leq N$.
• $ T_k $ is $ 1 $ or $ 2 $ $(1 \leq k \leq M)$.
• When $ T_k = 1 $,
• $1 \leq A_k \leq B_k \leq N$ $(1 \leq k \leq M)$.
• $1 \leq C_k < D_k \leq N$ $(1 \leq k \leq M)$.
• When $ T_k = 2 $,
• $1 \leq A_k < B_k \leq N$ $(1 \leq k \leq M)$.
• $1 \leq C_k \leq D_k \leq N$ $(1 \leq k \leq M)$.

Subtasks

1. ($ 4 $ points) $ M = 0 $.
2. ($ 12 $ points) $ T_k = 1 $, $ A_k = B_k = 1 $, $ C_k = D_k - 1 $, $ P = 1 $, $ R = 1 $ $(1 \leq k \leq M)$.
3. ($ 13 $ points) $ T_k = 1 $, $ A_k = B_k = 1 $, $ P = 1 $, $ R = 1 $ $(1 \leq k \leq M)$.
4. ($ 18 $ points) $N \leq 300$, $M \leq 300$.
5. ($ 53 $ points) No additional constraints.

Sample Explanation 1

We want to move from $ (2, 1) $ to $ (3, 7) $ in the shortest time. By moving along the path shown in the figure, we can warp everywhere except for the moves $ (2, 1) $ to $ (2, 2) $, $ (1, 4) $ to $ (2, 4) $, and $ (5, 7) $ to $ (4, 7) $, so it takes $ 3 $ byo to get from home to school. It is not possible to get from home to school in less time, so we output $ 3 $. This input/output example satisfies subtasks $ 4, 5 $.

Sample Explanation 2

This input/output example satisfies subtasks $ 3, 4, 5 $.

Sample Explanation 3

This input/output example satisfies subtasks $ 1, 2, 3, 4, 5 $.

见题面 Input 部分

见题面 Output 部分