BEARs

Time limit1sMemory limit128 MB

Summary

Determine the maximum guaranteed Chebyshev distance from the origin that a pursuer can force an evader to maintain on an infinite grid graph, given blocked main-street edges, using a game-theoretic reachability argument.

Level: Hard9 of 10
Topics: Graph, Game theory, BFS, Math
Solved: No attempts yet

Problem

The infinite city is cut into unit square blocks by infinitely many two-way streets running south–north and west–east. One south–north street is numbered $0$ ; the numbers increase to the east and decrease to the west. Likewise one west–east street is numbered $0$ ; the numbers increase to the north and decrease to the south.

Every intersection is labelled by the ordered pair of the numbers of the two streets that cross there (the first is the number of the south–north street). Some unit street sections are special and are called main streets.

While on patrol, sheriff Wolf spots a car carrying members of the notorious BEAR gang at intersection $(A, B)$ . The gang intends to break into the Honey Warehouse next to intersection $(0, 0)$ , and Wolf wants to keep them as far from it as he can.

The BEARs have not broken any law yet, so Wolf cannot arrest them; he can only obstruct them. Just before the BEARs enter an intersection, Wolf can get there first and block exactly one of the (up to four) unit sections meeting at that intersection — but he may never block a section that belongs to a main street. The BEARs still drive into the intersection, yet they cannot leave it through the blocked section. Wolf may block a different section at each intersection the gang enters. At the starting intersection $(A, B)$ the BEARs are already parked, so nothing is blocked there.

The distance from the warehouse is measured as $\max(|x|, |y|)$ . Find the largest value $D$ such that, no matter how the BEARs drive and no matter how Wolf blocks, every intersection $(x, y)$ the BEARs can reach satisfies $\max(|x|, |y|) \ge D$ . In other words, $D$ is the closest the BEARs can be forced to stay from the warehouse.

Input

The first line contains two integers $A$ and $B$ ( $|A| \le 10^6$ , $|B| \le 10^6$ ) — the starting intersection of the BEARs.

The second line contains one integer $N$ ( $0 \le N \le 500$ ) — the number of main streets.

Each of the next $N$ lines contains four integers $X_1, Y_1, X_2, Y_2$ ( $|X_i| \le 10^6$ , $|Y_i| \le 10^6$ ): every unit section between intersections $(X_1, Y_1)$ and $(X_2, Y_2)$ is a main street. Either $X_1 = X_2$ or $Y_1 = Y_2$ holds.

Output

Print a single integer: the maximum value of $D$ .

Note

In the first example the BEARs can reach an intersection at distance $1$ from the warehouse, but sheriff Wolf can stop them from ever getting any closer, so the answer is $1$ . Even if the BEARs keep trying forever, the sheriff can always keep them at distance at least $1$ . The figure illustrates one such approach.

Examples5

Example 1
Input
```
3 3
3
1 0 3 0
0 0 0 3
3 0 3 1
```
Expected output
```
1
```
Example 2
Input
```
3 3
0
```
Expected output
```
3
```
Example 3
Input
```
5 0
1
0 0 5 0
```
Expected output
```
0
```
Example 4
Input
```
5 0
1
1 0 5 0
```
Expected output
```
1
```
Example 5
Input
```
-3 -3
2
-3 0 -3 -3
0 0 -3 0
```
Expected output
```
0
```