Firma chce zakupić kwadratowy robot sprzątający do posprzątania prostokątnego pokoju. Niektóre części pokoju są zablokowane.

Dostępne są różne roboty o różnych rozmiarach. Każdy robot może poruszać się w poziomie i w pionie wewnątrz pokoju, o ile żadna część robota nie koliduje z przeszkodą. Roboty nie mogą zmieniać orientacji, więc ich ruchy są zawsze równoległe do osi układu współrzędnych. Większe roboty wykonują pracę szybciej, ale są bardziej narażone na blokowanie przez przeszkody. Robot musi zawsze znajdować się w całości wewnątrz pokoju, nie wystając poza krawędzie prostokąta.

Jaki jest największy robot, który może zakupić firma, aby był w stanie posprzątać wszystkie kwadraty w pokoju, które nie są zajęte przez przeszkody?

Wejście

Pierwsza linia wejścia zawiera trzy liczby całkowite $n, m$ ($3 \le n, m$ oraz $n \cdot m \le 5 \cdot 10^6$) oraz $k$ ($0 \le k < n \cdot m, k < 10^6$), gdzie $n$ i $m$ to wymiary pokoju w calach, a $k$ to liczba przeszkód.

Każda z kolejnych $k$ linii zawiera dwie liczby całkowite $i$ oraz $j$ ($1 \le i \le n, 1 \le j \le m$). Określają one, że jednocalowy kwadrat o współrzędnych $(i, j)$ jest zablokowany. Wszystkie zablokowane kwadraty są różne.

Wyjście

Wypisz pojedynczą liczbę całkowitą, która jest maksymalną długością boku największego kwadratowego robota, który mógłby posprzątać cały pokój, lub $-1$, jeśli żaden taki robot nie jest w stanie posprzątać całego pokoju.

Przykład

Wejście 1

10 7 1
8 3

Wyjście 1

2