背景

本题中的 $(a,b) \to (c,d)$ 代表一条从 $(a,b)$ 连向 $(c,d)$ 的线段。

题目描述

给定 $N$ 条长度为 $1$ 的线段，定义他们为「标记线」。

现在在点 $(A,B)$ 处有一个强盗，他要前往 $(0,0)$，警察们可以任意选择一个点，关闭他四周的任意一条线段。比如选择点 $(0,0)$，线段 $(-1,1) \to (1,1)$，$(-1,1)\to (-1,-1)$，$(-1,-1) \to (1,-1)$，$(1,-1) \to (1,1)$ 其中之一将会被关闭，但是关闭的线段中不能有与标记线 直接相连 的线段。比如 $(0,0) \to (0,2)$ 与 $(0,1) \to (0,3)$ 是直接相连的，但是 $(-1,1) \to (1,1)$ 与 $(0,0) \to (0,3)$ 不是。

强盗可以到达关闭的线段上的点，但是不能通过关闭的线段离开。

求强盗离 $(0,0)$ 的最近的距离的最大值 $D$。

输入格式

第一行两个整数 $A,B$ 代表强盗初始在 $(A,B)$。
第二行一个整数 $N$ 代表标记线数。
接下来 $N$ 行每行两个整数 $X_1,Y_1,X_2,Y_2$ 代表一条标记线 $(X_1,Y_1) \to (X_2,Y_2)$。

输出格式

一行一个整数代表强盗离 $(0,0)$ 的最近的距离的最大值 $D$。

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

1

提示

样例说明

对于样例 $1$，如下图所示：

选择的点为 $(0,0)$，关闭的线段为 $(1,1) \to (1,-1)$。

数据规模与约定

对于 $100\%$ 的数据，$|A|,|B|,|X_1|,|Y_1|,|X_2|,|Y_2| \le 10^6$，$0 \le N \le 500$，保证每条标记线 $X_1=X_2$ 或者 $Y_1=Y_2$。

说明

翻译自 BalticOI 2010 Day1 A BEARs。