ある会社が、長方形の部屋を掃除するために正方形の掃除ロボットを購入しようとしている。部屋の一部には障害物がある。

さまざまなサイズのロボットが存在する。各ロボットは、ロボットのどの部分も障害物と重ならない限り、部屋の中を水平および垂直に移動できる。ロボットは向きを変えることができないため、移動は常に軸に平行である。大きなロボットほど掃除を早く終えられるが、障害物に邪魔される可能性が高くなる。ロボットは常に部屋の中に完全に収まっていなければならず、長方形の端からはみ出してはならない。

障害物がない部屋のすべてのマスを掃除できる、購入可能な最大のロボットのサイズ（一辺の長さ）はいくらか。

入力

入力の最初の行には、3つの整数 $n, m$ ($3 \le n, m$ かつ $n \cdot m \le 5 \cdot 10^6$) と $k$ ($0 \le k < n \cdot m, k < 10^6$) が含まれる。ここで、$n$ と $m$ は部屋の寸法（インチ単位）であり、$k$ は障害物の数である。

続く $k$ 行のそれぞれには、2つの整数 $i$ と $j$ ($1 \le i \le n, 1 \le j \le m$) が含まれる。これは、$(i, j)$ にある1インチ四方のマスが障害物であることを示している。すべての障害物のあるマスは互いに異なる。

出力

部屋全体を掃除できる最大の正方形ロボットの一辺の長さを表す整数を1つ出力せよ。もしそのようなロボットが部屋全体を掃除できない場合は、$-1$ を出力せよ。

入出力例

入力 1

10 7 1
8 3

出力 1

2