配点: 100 点
問題
皮特兰是像围棋棋盘一样的结构,N \times N 由 个区划组成。从西边开始第 i (1 \leq i \leq N) 个,从北边开始第 j (1 \leq j \leq N) 个区划表示为 (i, j) 。另外,对于某个区划,如果在东西南北任意方向都相邻着其他区划,则称这些区划为该区划的邻区划。
高中生皮太郎是住在皮特兰的非常普通的彼得兔。或者说,更准确地说应该是曾经是。为了改善反复迟到的情况,试图后,皮太郎竟然获得了瞬移的能力。通常,皮太郎从一个区划步行到邻近区划需要 1 秒。但是,使用这种瞬移能力时,皮太郎可以在 0 秒内移动到邻近区划。
但是,Pitaro 使用太阳能来进行瞬移,所以并不是在任何地方、任何方向都可以瞬移。关于 Pitaro 可以瞬移的有阳光照射的范围,给出了 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) ,Pitaro 可以在双向上无限次瞬移。
- T_k = 2 时,A_k \leq i \leq B_k - 1 ,C_k \leq j \leq D_k 关于 (i, j) 和 在 (i + 1, j) ,Pitaro 可以在双向上无限次瞬移。
另外,由于 Pitaro 深夜很晚还没睡,可能会迟到。Pitaro 的家在 (P, Q) ,Pitaro 的学校在 (R, S) 。想要求出 Pitaro 从家到学校所需时间的最小值。
制約
- 输入全部为整数。
- 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).
小課題
- (4 点) M = 0.
- (12 点) T_k = 1,A_k = B_k = 1,C_k = D_k - 1,P = 1,R = 1 (1 \leq k \leq M).
- (13 点) T_k = 1,A_k = B_k = 1,P = 1,R = 1 (1 \leq k \leq M).
- (18 点) N \leq 300,M \leq 300.
- (53 点)没有额外的限制。
入力
输入是按以下格式从标准输入给出的。
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
出力
在标准输出中,输出 Pitaro 从家到学校所需时间的最小值(单位:秒)。 1 行。
入力例 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 的要求。