Naród Gridlandii można naturalnie przedstawić jako siatkę domów.

Gridlandia planuje zainstalować szereg wież komórkowych w niektórych punktach siatki. Kiedy mieszkaniec łączy się z danymi komórkowymi, jego telefon spróbuje połączyć się najpierw z najbliższą wieżą, a jeśli to się nie uda, z drugą najbliższą wieżą. Rząd Gridlandii obawia się, że niektóre wieże będą znacznie bardziej przeciążone niż inne. Pomóż im, obliczając dla każdego domu zarówno najbliższą, jak i drugą najbliższą wieżę komórkową, mierząc odległość za pomocą odległości Manhattan, która jest sumą różnicy wierszy i różnicy kolumn.

Wejście

Pierwsza linia wejścia zawiera trzy liczby całkowite $r, c$ ($1 \le r, c \le 500, r \cdot c \ge 2$) oraz $n$ ($2 \le n \le 2 \cdot 10^5$), gdzie Gridlandia jest siatką o $r$ wierszach i $c$ kolumnach, a $n$ to liczba wież komórkowych. Wieże są ponumerowane od $1$ do $n$.

Każda z kolejnych $n$ linii zawiera dwie liczby całkowite $i$ oraz $j$ ($1 \le i \le r, 1 \le j \le c$), które są pozycjami wież komórkowych w kolejności. Każda para $(i, j)$ będzie unikalna.

Wyjście

Pierwsze $r$ linii wyjścia powinno zawierać po $c$ liczb całkowitych oddzielonych spacjami. Liczba w $i$-tym wierszu i $j$-tej kolumnie powinna być numerem najbliższej wieży komórkowej dla pozycji $(i, j)$, mierzonej według odległości Manhattan.

Kolejne $r$ linii wyjścia powinno również zawierać po $c$ liczb całkowitych oddzielonych spacjami. Liczba w $i$-tym wierszu i $j$-tej kolumnie powinna być numerem drugiej najbliższej wieży komórkowej dla pozycji $(i, j)$, mierzonej według odległości Manhattan.

Jeśli istnieje wiele najbliższych wież komórkowych dla danej pozycji, wypisz tę z najniższym numerem. Podobnie, jeśli istnieje wiele drugich najbliższych wież komórkowych dla danej pozycji, wypisz tę z najniższym numerem.

Przykład

Wejście 1

4 8 3
1 1
4 1
2 6

Wyjście 1

1 1 1 1 3 3 3 3
1 1 1 3 3 3 3 3
2 2 2 3 3 3 3 3
2 2 2 2 3 3 3 3
2 2 3 3 1 1 1 1
2 2 3 1 1 1 1 1
1 1 1 2 2 2 2 2
1 1 1 3 2 2 2 2