题目描述

给定一个有 N 行 M 列的矩形表格。初始时所有格子都是白色的。

接下来有 Q 次操作。每次操作会把同一行或同一列上的一个或多个连续格子染成黑色。若某个格子至少被染黑过一次，那么最终它就是黑色。

请在所有染色操作都执行完毕后，求只由白色格子组成的最大正方形的边长。
表格左上角坐标为 (1, 1)。

输入格式

第一行输入两个正整数 N 和 M，表示表格的行数和列数。
第二行输入一个正整数 Q，表示操作数。
接下来 Q 行，每行输入四个整数 Xi1, Yi1, Xi2, Yi2。满足条件的所有格子 (X, Y)：

• Xi1 <= X <= Xi2
• Yi1 <= Y <= Yi2

都会被染成黑色。

输出格式

输出一个整数，表示由全白格子组成的最大正方形的边长。

数据范围

• 1 <= N, M <= 10^9
• 1 <= Q <= 50 000
• 1 <= Xi1 <= Xi2 <= N
• 1 <= Yi1 <= Yi2 <= M
• 对每个操作，都有 Xi1 = Xi2 或 Yi1 = Yi2

子任务

只有当某个子任务中的所有测试全部通过时，才能获得该子任务的分数。

样例

输入

6 5
4
1 2 1 5
1 4 5 4
5 2 5 2
1 2 1 5

输出

3

样例解释

原题在此处给出了一张表格示意图，用 X 标出被染黑的格子，从而说明答案为 3。
此处应插入原题样例说明示意图。