JOI-kun 正在一个特殊的球场练习高尔夫。

这个球场是一个 $xy$ 坐标平面。球场上有 $N$ 个障碍物。第 $i$ 个障碍物（$1 \le i \le N$）占据了一个矩形区域，其 $x$ 坐标满足 $A_i \le x \le B_i$，且 $y$ 坐标满足 $C_i \le y \le D_i$。任意两个障碍物（包括它们的边界）互不相交。

在这个球场中，起点为 $(S, T)$，终点为 $(U, V)$。这两个点互不相同，且不包含在任何障碍物及其边界内。起初，高尔夫球放置在起点。

JOI-kun 可以击打高尔夫球，使其沿平行于坐标轴的四个方向之一移动任意距离。但是，球的轨迹不能接触任何障碍物的内部。球可以穿过障碍物的边界，也可以停在障碍物的边界上。之后，他可以通过击球改变方向，向没有障碍物的方向移动。

JOI-kun 想知道完成球场所需的最小击球次数。作为 JOI-kun 的高尔夫球友，他请你计算这个次数。

从起点到终点移动高尔夫球所需的最小击球次数是多少？

题目描述

给定高尔夫球场的信息，编写一个程序，计算将高尔夫球从起点移动到终点所需的最小击球次数。

输入格式

从标准输入读取以下数据。

• 第一行包含四个空格分隔的整数 $S, T, U, V$。这意味着起点的 $x$ 坐标为 $S$，起点的 $y$ 坐标为 $T$，终点的 $x$ 坐标为 $U$，终点的 $y$ 坐标为 $V$。
• 第二行包含一个整数 $N$，即障碍物的数量。
• 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含四个空格分隔的整数 $A_i, B_i, C_i, D_i$。这意味着第 $i$ 个障碍物占据的矩形区域满足 $A_i \le x \le B_i$ 且 $C_i \le y \le D_i$。

输出格式

向标准输出写入一行。输出包含将高尔夫球从起点移动到终点所需的最小击球次数。

数据范围

所有输入数据满足以下条件：

• $1 \le S \le 1\,000\,000\,000$
• $1 \le T \le 1\,000\,000\,000$
• $1 \le U \le 1\,000\,000\,000$
• $1 \le V \le 1\,000\,000\,000$
• $1 \le N \le 100\,000$
• $1 \le A_i < B_i \le 1\,000\,000\,000$ ($1 \le i \le N$)
• $1 \le C_i < D_i \le 1\,000\,000\,000$ ($1 \le i \le N$)
• $(S, T) \neq (U, V)$
• 任意两个障碍物（包括它们的边界）互不相交。
• 起点和终点不包含在任何障碍物及其边界内。

子任务

共有 3 个子任务。各子任务的分数和附加限制如下：

子任务 1 [10 分]

• $S \le 1\,000$
• $T \le 1\,000$
• $U \le 1\,000$
• $V \le 1\,000$
• $N \le 1\,000$
• $B_i \le 1\,000$ ($1 \le i \le N$)
• $D_i \le 1\,000$ ($1 \le i \le N$)

子任务 2 [20 分]

• $N \le 1\,000$

子任务 3 [70 分]

• 无附加限制。

样例

样例输入 1

3 5 8 6
1
5 6 2 8

样例输出 1

3

说明 1

在此样例输入中，例如，JOI-kun 可以将高尔夫球按 $(3,5) \to (3,2) \to (8,2) \to (8,6)$ 的路径从起点移动到终点；他需要三次击球。由于不可能用少于三次的击球移动球，因此输出 3。

样例输入 2

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

样例输出 2

1

说明 2

在此样例输入中，JOI-kun 需要一次击球即可将高尔夫球从起点移动到终点。

样例输入 3

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

样例输出 3

4