题目描述

译自 JOI Open 2017 T3 「ゴルフ / Golf」

平面的第一象限上有 $$N$$ 个矩形障碍，矩形的两组对边分别平行于 $$x$$ 轴和 $$y$$ 轴。矩形 $$i(1\le i\le N)$$ 的左下角是 $$(A_i, C_i)$$，右上角是 $$(B_i, D_i)$$。任意两个矩形（包括边界）不相交。
JOI 君需要将一个高尔夫球从 $$(S,T)$$ 打到 $$(U,V)$$，保证这两点不同，保证这两点不在障碍内或障碍的边界上。

JOI 君只能朝平行于 $$x$$ 轴或平行于 $$y$$ 轴的方向击球。每次击球后，球会沿直线运动。
在球运动过程中，JOI 君可以随时让球停下（即使球不在障碍物边界上），然后朝另一个方向再次击球。
如果球在运动过程中撞到某个障碍物的边界，它会立即停下，并且不能继续进入障碍物内部。
当然，球可以经过障碍物的边界，但不能进入障碍物内部。

求最少要击球多少次，才能将高尔夫球从 $$(S,T)$$ 打到 $$(U,V)$$。

输入格式

第一行有四个整数 $S, T, U, V$。
第二行有一个整数 $N$。
在接下来的 $N$ 行中，每行有四个整数 $A_i, B_i, C_i, D_i$。

输出格式

输出一行，一个整数，表示最少击球次数。

3 5 8 6
1
5 6 2 8

3

1 1 1 10
3
5 6 2 8
1 2 2 3
8 10 3 5

1

20 68 85 74
5
30 70 14 100
5 24 15 67
75 86 75 79
75 90 19 62
93 98 26 58

4

提示

样例解释 1

$(3,5) → (3,2) → (8,2) → (8,6)$

数据范围

$1\le S, T, U, V\le 10^9, 1\le N\le 10^5, 1\le A_i<B_i\le 10^9, 1\le C_i<D_i\le 10^9,$ $(S,T)≠(U,V)$。

• 子任务 #1（10 分）：$S, T, U, V, N, B_i, D_i\le 1000$；
• 子任务 #2（20 分）：$N\le 1000$；
• 子任务 #3（70 分）：没有额外限制。