問題

ピーターランドは碁盤の目のような構造になっており，N \times N 個の区画からなる．西から i (1 \leq i \leq N) 番目，北から j (1 \leq j \leq N) 番目の区画を (i, j) と表す．また，ある区画に対して，東西南北いずれかに隣接している区画をその区画の隣の区画と呼ぶ．

高校生のピ太郎はピーターランドに住むごく普通のピーターラビットである．いや，であったというのが正しいであろうか．度重なる遅刻を改善しようと試みた結果，ピ太郎はワープすることができるようになってしまったのである．ピ太郎は通常，ある区画から隣の区画へ徒歩で移動するのに 1 ビョウかかる．しかし，このワープ能力を用いるとピ太郎は隣の区画へ 0 ビョウで移動することができる．

ただし，ピ太郎は太陽のエネルギーを使ってワープするので，どこでも，どの方向にでもワープができるわけではない．ピ太郎がワープできる日当たりの良い範囲に関する M 個の情報が与えられる．k 個目の情報 (1 \leq k \leq M) では整数 T_k, A_k, B_k, C_k, D_k が与えられ，次のことを意味する．

• T_k = 1 のとき，A_k \leq i \leq B_k ，C_k \leq j \leq D_k - 1 について，ピ太郎は (i, j) と (i, j + 1) を双方向に好きなだけワープできる．
• T_k = 2 のとき，A_k \leq i \leq B_k - 1 ，C_k \leq j \leq D_k について，ピ太郎は (i, j) と (i + 1, j) を双方向に好きなだけワープできる．

ピ太郎はまた深夜遅くまで起きていたせいで学校に遅刻しそうである．ピ太郎の家は (P, Q) に，ピ太郎の学校は (R, S) にある．ピ太郎が家から学校に行くのにかかる時間の最小値を求めたい．

制約

• 入力はすべて整数である．
• 1 \leq N \leq 1\,000\,000\,000．
• 0 \leq M \leq 1\,000．
• 1 \leq P, Q, R, S \leq N．
• T_k は 1 または 2 (1 \leq k \leq M)．
• 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)．
• 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)．

小課題

1. (4 点) M = 0．
2. (12 点) T_k = 1，A_k = B_k = 1，C_k = D_k - 1，P = 1，R = 1 (1 \leq k \leq M)．
3. (13 点) T_k = 1，A_k = B_k = 1，P = 1，R = 1 (1 \leq k \leq M)．
4. (18 点) N \leq 300，M \leq 300．
5. (53 点) 追加の制約はない．

入力例 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

出力例 1

3

(2, 1) から (3, 7) まで最短時間で移動したい．この時，図のような経路で移動すると，(2, 1) - (2, 2) の移動と (1, 4) - (2, 4) の移動と (5, 7) - (4, 7) の移動以外はすべてワープで済むので，3 ビョウで家から学校まで移動することができる．また，これより短い時間で家から学校へ行くことはできないので，3 を出力する．

この入出力例は小課題 4, 5 を満たしている．

入力例 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

出力例 2

2

この入出力例は小課題 3, 4, 5 を満たしている．

入力例 3

12 0
1 3 1 11

出力例 3

8

この入出力例は小課題 1, 2, 3, 4, 5 を満たしている．