In the city of the future, Innopolis, construction is still going on, but n buildings have already been built. The roof of each building can be represented as a rectangle with sides parallel to the coordinate axes. No buildings touch or intersect.
Inna loves to walk on rooftops. She is standing on the roof of building number 1 and wants to get on the roof of building number n.
Inna can be represented as a point on a plane. It can move around the roof without leaving its borders, but it cannot be on the roof border. She can also jump from rooftop to rooftop, but only in directions parallel to the coordinate axes. For safety reasons, Inna cannot jump over buildings, that is, at any moment of the jump, there should not be a building under her.
Help Inna calculate the minimum number of times she has to jump from one roof to another to get to building number n.
Input data format
The first line contains a natural number n — number of buildings in Innopolis (n<= 10
5). The next n lines contain the roofs of the buildings. Each of these lines contains four integers x
i1, y
i1, x
i2 and y
i2 — coordinates of opposite vertices of the rectangle describing the roof of the building (x
i1 < x
i2; y
i1 < y
i2 ) It is guaranteed that no two rectangles have common points. All coordinates — non-negative integers and <= 10
9
Output data format
Print a single integer — the minimum number of jumps that Inna must make to get from the roof of building 1 to the roof of building n. If Inna can't get to the roof of the n-th building, print -1.
|
Enter |
Output |
4
0 0 3 2
1 6 4 8
1 3 4 5
7 7 10 9
|
3 |
3
0 0 3 2
1 3 4 5
7 7 10 9
|
-1 |