一間公司希望購買一台正方形的清潔機器人來清潔一間長方形的房間。房間內的部分區域有障礙物。

市面上有各種不同尺寸的機器人。每台機器人若在不與任何障礙物重疊的情況下，可以在房間內進行水平與垂直移動。機器人無法改變方向，因此移動始終與座標軸平行。較大的機器人能更快完成工作，但更容易受到障礙物的阻礙。機器人必須始終完全位於房間內，且不得超出長方形的邊界。

公司能購買的、能夠清潔房間內所有未被障礙物佔據之方格的最大正方形機器人，其邊長為何？

輸入格式

輸入的第一行包含三個整數 $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$ 行，每行包含兩個整數 $i$ 和 $j$ ($1 \le i \le n, 1 \le j \le m$)。這表示位於 $(i, j)$ 的一平方英吋方格有障礙物。所有被阻擋的方格皆不相同。

輸出格式

輸出一個整數，代表能清潔整個房間的最大正方形機器人的邊長；若沒有任何機器人能清潔整個房間，則輸出 $-1$。

範例

輸入 1

10 7 1
8 3

輸出 1

2