Walk

Finding your destination in a big, unfamiliar city can be hard, especially for a computer scientist like Kirk, who always insists on taking the shortest possible route. Planning ahead helps: given a map of the city, Kirk wants to find a shortest path from his current position to his destination.

The map of the city is an infinite grid of unit squares in the plane.

Kirk is currently located at the square $(0, 0)$, and his destination is the square $(X, Y)$.

There are $N$ buildings in the city. Each building is a rectangle that fully occupies a set of unit squares. No two buildings touch or overlap, so Kirk can walk freely around every building. Each building is given by the coordinates of two diagonally opposite squares that it occupies.

In one step Kirk can walk to one of the four squares adjacent up, down, left, or right, but he may never step onto a square occupied by a building. His current position is the west entrance to the city, and the $x$ coordinate of every square occupied by a building is strictly greater than $0$.

Given the locations of the buildings, write a program that finds the length of a shortest path from Kirk's current position to his destination. The length of a path is the number of squares on it, excluding the starting square.

The first line contains two integers $X$, $Y$ — the coordinates of the destination square ($1 \le X \le 10^6$, $-10^6 \le Y \le 10^6$).

The second line contains a single integer $N$ — the number of buildings ($0 \le N \le 100,000$).

Each of the following $N$ lines contains four integers $X_1$, $Y_1$, $X_2$, $Y_2$ — the coordinates of two diagonally opposite squares occupied by one building ($1 \le X_1, X_2 \le 10^6$, $-10^6 \le Y_1, Y_2 \le 10^6$).

Print a single integer $L$ — the length of a shortest path, i.e. the number of squares on a shortest path from $(0, 0)$ to $(X, Y)$, excluding the starting square.

Because no two buildings touch, the walkable squares are all connected, so the destination is always reachable and the length of a shortest path is uniquely determined.

The figures below show a shortest path for each example.