Une entreprise souhaite acheter un robot de nettoyage de forme carrée pour nettoyer une pièce de forme rectangulaire. Certaines parties de la pièce sont obstruées.

Il existe différents robots de tailles différentes. Chaque robot peut se déplacer horizontalement et verticalement dans la pièce si aucune partie du robot n'intersecte un obstacle. Ils sont incapables de changer d'orientation, les mouvements sont donc toujours alignés sur les axes. Les robots plus grands effectueront le travail plus rapidement, mais sont plus susceptibles d'être gênés par des obstacles. Le robot doit toujours rester entièrement à l'intérieur de la pièce, sans qu'aucune partie ne dépasse les bords du rectangle.

Quelle est la taille du plus grand robot que l'entreprise peut acheter qui sera capable de nettoyer tous les carrés de la pièce non occupés par des obstacles ?

Entrée

La première ligne de l'entrée contient trois entiers $n$, $m$ ($3 \le n, m$ et $n \cdot m \le 5 \cdot 10^6$) et $k$ ($0 \le k < n \cdot m$, $k < 10^6$), où $n$ et $m$ sont les dimensions de la pièce en pouces, et $k$ est le nombre d'obstacles.

Chacune des $k$ lignes suivantes contient deux entiers $i$ et $j$ ($1 \le i \le n$, $1 \le j \le m$). Cela précise que le carré d'un pouce situé en $(i, j)$ est obstrué. Tous les carrés obstrués sont distincts.

Sortie

Affichez un seul entier, qui est la longueur maximale d'un côté du plus grand robot de forme carrée capable de nettoyer toute la pièce, ou $-1$ si aucun robot de ce type ne peut nettoyer toute la pièce.

Exemples

Entrée 1

10 7 1
8 3

Sortie 1

2