题目描述

2034年，某中学决定修建校庆100周年纪念碑，作为杰出校友的你被找了过来，帮校方确定纪念碑的选址.中学的土地可以看作是一个长为$n$、宽为$m$的矩形。它由$n×m$个$1×1$的正方形组成，其中左下角的正方形的坐标为($1,1$)，右上角的正方形的坐标为($n, m$)。其中有一些土地已经被用来修建建筑物，每一幢建筑物都可以看做是一个左下角为($x_1,y_1$)，右上角为($x_2,y_2$)的矩形。纪念碑可以看作是一个正方形。校方希望你找出一块最大的正方形区域供他们参考。

输入

每一组数据的第一行包含三个整数$n,m$和$p$，分别表示学校土地的长、宽以及建筑物的数量。接下来的$p$行，每行包含四个整数$x_1、y_1、x_2、y_2$，分别表示每一幢建筑物左下角以及右上角的坐标。

输出

输出一个数，表示可能的正方形最大边长。。

输入样例

13 5 8
8 4 10 4
4 3 4 4
10 2 12 2
8 2 8 4
2 4 6 4
10 3 10 4
12 3 12 4
2 2 4 2

输出样例

3

提示

【数据规模】 对于30%的数据，$p≤1000$。 对于70%的数据，$p≤30000$。 对于100%的数据，$p≤400000，m,n≤1000000$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。