405010: GYM101736 J Journey

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.

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 a_i, b_i, x_i, and y_i ( - 10⁶ ≤ a_i < x_i ≤ 10⁶; - 10⁶ ≤ b_i < y_i ≤ 10⁶), 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 A_x, A_y, B_x, B_y ( - 10⁶ ≤ A_x, A_y, B_x, B_y ≤ 10⁶), 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.

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.

3
0 0 1 1
0 1 1 2
1 -1 5 0
0 -1 2 1

5.4142135624