On an endless sheet of checked paper there are axes of coordinates. A unit for measurement in this coordinates system is the length of the square’s edge. Also there are *N* rectangles on this sheet of paper. Their edges are parallel to the coordinate axis, and go through the borders between the squares. If we denote the coordinates of the lower left corner of the *i*-th rectangle with (*x*_{i}, *y*_{i}), and the coordinates of its upper right corner with (*x*^{i}, *y*^{i}), we will see, that:

*x*_{1} = 0, *y*_{1} = 0

*x*^{i} = *x*_{i + 1}

2 ≤ *x*^{i} − *x*_{i} ≤ 100

2 ≤ *y*^{i} − *y*_{i} ≤ 100

If two rectangles with numbers *i* and *i* + 1 overlap, their common border disappears:

A traveler starts his way from the point with the coordinates (1, 1), which, as it follows from the rules above, certainly lays in the first rectangle. The traveler walks strictly along the edges of the squares. He is not allowed to walk on the borders of the rectangles. Thus, he can leave one rectangle for another only through their disappeared common border. There is an example of some beginning of his walk on the picture.

The traveler’s goal is the point (*x*^{n} − 1, *y*^{n} − 1), which is obviously situated inside the last rectangle.

### Input

In the first line there is a positive integer *n*, 0 < *n* < 100000 — the number of rectangles on the plane. Then *n* lines follow, each one of them containing four integer numbers *x*_{i}, *y*_{i}, *x*^{i}, *y*^{i}, separated with spaces, satisfying the above rules.

### Output

You should output the length (the measurement unit is the edge of one square) of the shortest possible route for the traveler to go from the point (1, 1) to the point (*x*^{n} − 1, *y*^{n} − 1), or the number −1, if there exists no such route (the latter possibility is realized, for instance, on the picture).

### Sample

input | output |
---|

2
0 0 3 5
3 1 5 7 | 8 |

**Problem Author: **Leonid Volkov

**Problem Source: **USU Internal Contest, March 2002