TooDee's Fastest Route Home

TooDee is a two‐dimensional grid land, much like the famous Cartesian plane. In TooDee, many little creatures called Dee live. These creatures fly strictly on the 2D grid under very civilized rules. The beehives in TooDee are rectangular with edges parallel to the coordinate axes. That is, each beehive has its sides aligned along the east–west or north–south directions.

Dee have fixed flight trajectories made up of line segments parallel to the axes, and these segments intersect only at points with integer coordinates. When flying in TooDee, a Dee must obey the following rules (all coordinates are integers):

1. If currently at point \( (X, Y) \), the next step can only be to one of the four adjacent points: \( (X, Y-1) \), \( (X, Y+1) \), \( (X-1, Y) \), or \( (X+1, Y) \).
2. The Dee is not allowed to enter the interior of any beehive.
3. The Dee can change its flying direction only when it is exactly on a beehive's boundary (i.e. on an edge or at a corner of a beehive).
4. At the start, the Dee may choose any initial direction.

Tonight is the birthday of the daughter of the Public Finance Minister, Deeficer. She wants to get home as quickly as possible. Given that she flies at a speed of one unit per second, help her find the fastest route home.

Note: A beehive is given as a rectangle with its lower‐left and upper‐right corners provided. A point \( (x,y) \) is considered to be inside a beehive if for any beehive with corners \( (x_1,y_1) \) and \( (x_2,y_2) \), it satisfies \( x_1 < x < x_2 \) and \( y_1 < y < y_2 \). However, points on the boundary (where \( x=x_1 \), \( x=x_2 \), \( y=y_1 \), or \( y=y_2 \) with the other coordinate in range) are allowed.

inputFormat

The input is given as follows:

• The first line contains an integer \(N\) representing the number of beehives.
• Then \(N\) lines follow, each containing four integers \(x_1\ y_1\ x_2\ y_2\) representing a beehive. Here, \( (x_1,y_1) \) is the lower‐left corner and \( (x_2,y_2) \) is the upper‐right corner of the beehive.
• The next line contains two integers representing the starting point coordinates.
• The final line contains two integers representing the destination point coordinates (home).

It is guaranteed that all coordinates are integers.

outputFormat

Output a single integer, the minimum number of seconds required for the Dee to get home. If it is impossible to reach home under the given conditions, output -1.

sample

0
0 0
2 0

2