AT_otemae2019_g 空をかけるピ太郎 (Pitaro, who Leaps through Air)

[problemUrl]: https://atcoder.jp/contests/otemae2019/tasks/otemae2019_g ピーターランドは碁盤の目のような構造になっており，$ 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) $ にある．ピ太郎が家から学校に行くのにかかる時間の最小値を求めたい．

入力は以下の形式で標準入力から与えられる． > $ 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 $

標準出力に，ピ太郎が家から学校に行くのにかかる時間の最小値(単位:ビョウ)を $ 1 $ 行で出力せよ．

### 制約 - 入力はすべて整数である． - $ 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\