无限城市被无数条南北向和东西向的双向街道划分为单位正方形街区。其中一条南北向街道被标记为 $0$，街道编号向东递增，向西递减。类似地，其中一条东西向街道被标记为 $0$，编号向北递增，向南递减。

每个交叉路口由相交街道的有序数对表示（第一个是南北向街道的编号，第二个是东西向街道的编号）。一些街道线段更重要，被称为主干道。

一天，警长 Wolf（无限城市最凶猛的守护者）正在街上巡逻，在交叉路口 $(A, B)$，他注意到一辆载有著名的 BEAR 帮派成员的汽车。Wolf 听说 BEAR 帮计划潜入位于交叉路口 $(0, 0)$ 附近的城市蜂蜜仓库，并决定阻止他们。

然而，他们到目前为止还没有犯下任何罪行，Wolf 不能逮捕他们。但他有权在任何交叉路口停下他的车，并封锁在该交叉路口相交的四个单位线段中的恰好一个。然而，他不能封锁属于主干道的单位线段。

因此，Wolf 决定追捕 BEAR 帮。就在他们到达某个交叉路口之前，他可以超越他们的车，并封锁该交叉路口处的四个单位线段之一。BEAR 帮将能够驶入该交叉路口，但他们将无法从该交叉路口驶向被警长车辆封锁的线段。

警长希望让 BEAR 帮尽可能远离蜂蜜仓库。求最大距离 $D$，使得 BEAR 帮可能到达的任何交叉路口 $(x, y)$ 都满足条件 $\max(|x|, |y|) \ge D$。

输入格式

第一行包含两个整数：$A$ 和 $B$（$|A| \le 10^6$，$|B| \le 10^6$），表示 BEAR 帮的起点。

第二行包含一个整数 $N$（$0 \le N \le 500$），表示主干道的数量。

接下来的 $N$ 行，每行包含四个整数：$X_1, Y_1, X_2, Y_2$（$|X_i| \le 10^6$，$|Y_i| \le 10^6$），表示交叉路口 $(X_1, Y_1)$ 和 $(X_2, Y_2)$ 之间的街道线段是一条主干道。保证 $X_1 = X_2$ 或 $Y_1 = Y_2$ 成立。

输出格式

输出仅一行，包含 $D$ 的最大值。

样例

输入样例 1

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

输出样例 1

1

说明

下图展示了 BEAR 帮如何到达距离仓库为 1 的范围内：

尽管 BEAR 帮可以永远继续尝试，但警长可以阻止他们进一步靠近仓库。