Description

You are given $N$ line segments of length $1$, defined as “marked segments”.

Now there is a robber at point $(A,B)$, and he wants to go to $(0,0)$. The police may choose any point and block any one line segment around it. For example, if they choose point $(0,0)$, then one of the following segments will be blocked: $(-1,1) \to (1,1)$, $(-1,1)\to (-1,-1)$, $(-1,-1) \to (1,-1)$, $(1,-1) \to (1,1)$. However, among the segments that are blocked, there must not be any segment that is directly connected to a marked segment. For example, $(0,0) \to (0,2)$ and $(0,1) \to (0,3)$ are directly connected, but $(-1,1) \to (1,1)$ and $(0,0) \to (0,3)$ are not.

The robber may reach points on a blocked segment, but he cannot leave by crossing the blocked segment.

Find the maximum value $D$ of the robber’s minimum distance to $(0,0)$.

Input Format

The first line contains two integers $A,B$, representing that the robber initially is at $(A,B)$.
The second line contains one integer $N$, representing the number of marked segments.
The next $N$ lines each contain four integers $X_1,Y_1,X_2,Y_2$, representing a marked segment $(X_1,Y_1) \to (X_2,Y_2)$.

Output Format

Output one integer, representing the maximum value $D$ of the robber’s minimum distance to $(0,0)$.

3 3
3
1 0 3 0
0 0 0 3
3 0 3 1

1

Hint

Sample Explanation

For sample $1$, as shown in the figure below:

The chosen point is $(0,0)$, and the blocked segment is $(1,1) \to (1,-1)$.

Constraints

For $100\%$ of the testdata, $|A|,|B|,|X_1|,|Y_1|,|X_2|,|Y_2| \le 10^6$, $0 \le N \le 500$. It is guaranteed that for each marked segment, $X_1=X_2$ or $Y_1=Y_2$.

Note

Translated from BalticOI 2010 Day1 A BEARs.

Translated by ChatGPT 5