Background

The transportation system in the capital of JSOI is very complex. JYY is currently thinking about how to quickly reach the meeting place with the princess.

Description

There are $N$ streets in the capital of JSOI, and each street is a line segment that is either vertical or horizontal. JYY starts from $(sx, sy)$ and hopes to reach $(tx, ty)$.

JYY can only move horizontally or vertically along the streets. If a point lies on two line segments simultaneously, JYY can switch from one street to another at this point.

JYY hopes you can help him calculate the shortest path distance.

Input

The first line contains a positive integer $N$, representing the number of streets.

The following $N$ lines each contain 4 integers $xi_1, yi_1, xi_2, yi_2$, representing that the $i$-th street is from $(xi_1, yi_1)$ to $(xi_2, yi_2)$.

The $(N+2)$-th line contains 4 integers $sx, sy, tx, ty$, representing the starting point and the destination. It is guaranteed that the starting point and the destination lie on some street.

Output

Output an integer representing the length of the shortest path. It is guaranteed that the input has a solution.

Constraints

• For 30% of the data, $N \le 200$.
• For 100% of the data, $N \le 10000$.
• The input guarantees that every street is either horizontal or vertical, and no two streets overlap (any two streets have at most one intersection point). All coordinates have absolute values less than or equal to $10^9$.

Examples

Input 1

8
0 0 0 2
0 2 2 2
2 2 2 0
2 0 0 0
-1 1 1 1
1 1 1 3
1 3 -1 3
-1 1 -1 3
2 0 -1 3

Output 1

6