题目描述

Steve 经营着一家牧场。牧场可以看成一个无限大的网格，Steve 将所有的行从上到下用整数 $...,−2,−1,0,1,2,...$ 编号，所有的列从左到右也用整数 $...,−2,−1,0,1,2,...$ 编号，行 $i$ 列 $j$ 的格子记为 $(i,j)$。如果两个格子有一条公共边，则称两个格子相邻。

为了便于管理，Steve 在牧场中安装了一些栅栏，这些栅栏构成了 $n$ 个矩形，第 $i$ 个矩形的左上角为 $(a_i,b_i)$，右下角为 $(c_i,d_i)$（$c_i−a_i≥2$，$d_i−b_i≥2$），栅栏将占据第 $a_i$ 行和第 $c_i$ 行位于第 $b_i$ 至 $d_i$ 列的格子以及第 $b_i$ 列和第 $d_i$ 列位于第 $a_i$ 至 $c_i$ 行的格子。特别地，Steve 保证任意两个矩形占据的格子没有公共点。

Steve 可以乘坐骑往相邻的格子移动，不过如果要进入有栅栏占据的格子，则必须将该格子的栅栏门打开。由于开栅栏门是一件比较麻烦的事情，Steve 想知道从 $(xS,yS)$ 出发到达 $(xT,yT)$，至少要打开多少次栅栏门。

输入格式

输入第一行包含一个正整数 $n$，表示栅栏构成的矩形个数。

接下来 $n$ 行，每行四个整数 $a_i,b_i,c_i,d_i$，每两个整数之间用一个空格隔开，描述一个左上角为 $(a_i,b_i)$，右下角为 $(c_i,d_i)$ 的矩形。

最后一行包含四个整数 $xS,yS,xT,yT$，每两个整数之间用一个空格隔开，表示起点和终点的位置。保证 $(xS,yS)$ 和 $(xT,yT)$ 未被任何栅栏占据。

输出格式

输出共一行，包含一个整数，表示打开栅栏门的最小次数。

输入样例 1

4
-6 -7 3 1 
0 3 4 6 
-4 -5 -2 -2 
-5 4 -3 6 
-3 -4 3 5 

输出样例 1

3

输入输出样例 1 说明

从 $(−3,−4)$ 到 $(3,5)$ 至少需要打开 $3$ 个栅栏门。

输入样例 2

2
1 1 3 3 
1 5 3 7 
2 0 2 8 

输出样例 2

0

输入输出样例 2 说明

不用经过任何栅栏即可从 $(2,0)$ 走到 $(2,8)$。

数据规模与约定

对于 $30\%$ 的数据，$n≤4$，$0≤a_i,b_i,c_i,d_i≤100$，$0≤xS,yS,xT,yT≤100$；

对于 $50\%$ 的数据，$n≤500$，$0≤a_i,b_i,c_i,d_i≤2,000$，$0≤xS,yS,xT,yT≤2,000$；

对于 $80\%$ 的数据，$n≤20,000$；

对于 $100\%$ 的数据，$n≤500,000$，$−10^9≤a_i,b_i,c_i,d_i≤10^9$，$c_i≥a_i+2$，$d_i≥b_i+2$，$−10^9≤xS,yS,xT,yT≤10^9$。