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

彼得兰德是一个类似棋盘格的城市，划分为 $N \times N$ 个小区域。我们用 $(i, j)$ 来表示从西往东第 $i$ 列、从北往南第 $j$ 行的区域。每个区域可以与其东、西、南、北相邻的区域互通，我们称之为相邻区。 彼得郎是一只住在彼得兰德的彼得兔。他原本与其他兔子无异，直到他不断尝试解决迟到的问题，意外获得了瞬移能力。在普通情况下，他从当前区域步行到相邻区域需要 $1$ 秒。但使用瞬移的话，可以瞬间抵达——所需时间为 $0$ 秒。 不过，彼得郎的瞬移能力受太阳能量的限制，无法自由选择任何地方和方向。我们会给出 $M$ 条阳光充足的可以瞬移的区域信息。每条信息第 $k$ 条由整数 $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$ $\dots$ $T_M$ $A_M$ $B_M$ $C_M$ $D_M$

输出彼得郎从家到学校所需的最短时间（单位：秒）。

- 所有输入均为整数。 - $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 彼得郎想从 $(2, 1)$ 移动到 $(3, 7)$，并希望用最短的时间完成。按图上的路径移动，除了在 $(2, 1) - (2, 2)$、$(1, 4) - (2, 4)$ 和 $(5, 7) - (4, 7)$ 处需要步行，其余路径都可以瞬移，因此总共只需 $3$ 秒。这是到达学校的最快方案，因此输出 $3$。!路径示例在 [此处](https://img.atcoder.jp/otemae2019/0a6feeaeefa2b34d220eff71b61892bc.png)。此例满足子任务 4 和 5。 ### 样例解释 2 此例满足子任务 3、4、5。 ### 样例解释 3 此例满足所有子任务 1、2、3、4、5。 **本翻译由 AI 自动生成**