J. Journey
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The little green Cactus is on his daily run through the cactus desert. As usual, he is coding problem J as he runs. However, he forgot his charger today, and his computer is running out of battery. Now Cactus must run from point A (his current location) to point B (the location of his charger).

There are n oddly rectangular cacti in the desert, and Cactus cannot run through these cacti. No two cacti overlap, but they may touch at a point or on a line segment. Cactus cannot run through the points where two cacti touch. Find the minimum distance that Cactus must run to get from A to B.

Input

The first line of input contains a single integer n (0 ≤ n ≤ 100), the number of cacti.

Each of the next n lines contains four space-separated integers ai, bi, xi, and yi ( - 106 ≤ ai < xi ≤ 106; - 106 ≤ bi < yi ≤ 106), describing the bottom left and the top right corners of the cactus (on the Cartesian plane).

The last line of input contains four space-separated integers Ax, Ay, Bx, By ( - 106 ≤ Ax, Ay, Bx, By ≤ 106), describing point A and point B. It is guaranteed that A and B do not lie in the interior or on the boundary of a cactus.

Output

Print the minimum distance Cactus must run, or  - 1 if he cannot run from A to B. The answer will be considered correct if the relative or absolute error is at most 10 - 6.

Example
Input
3
0 0 1 1
0 1 1 2
1 -1 5 0
0 -1 2 1
Output
5.4142135624