Страну Гридландию можно естественным образом представить как сетку домов.

Гридландия планирует установить несколько вышек сотовой связи в некоторых точках сетки. Когда житель подключается к мобильному интернету, его телефон сначала пытается подключиться к ближайшей вышке, а если это не удается — ко второй по близости. Правительство Гридландии обеспокоено тем, что некоторые вышки будут перегружены гораздо сильнее других. Помогите им, вычислив для каждого дома ближайшую и вторую по близости вышку сотовой связи, измеряя расстояние по Манхэттену, которое равно сумме абсолютных разностей координат по строкам и столбцам.

Входные данные

Первая строка входных данных содержит три целых числа $r, c$ ($1 \le r, c \le 500, r \cdot c \ge 2$) и $n$ ($2 \le n \le 2 \cdot 10^5$), где Гридландия представляет собой сетку из $r$ строк и $c$ столбцов, а $n$ — количество вышек сотовой связи. Вышки пронумерованы от $1$ до $n$.

Каждая из следующих $n$ строк содержит два целых числа $i$ и $j$ ($1 \le i \le r, 1 \le j \le c$), которые являются позициями вышек сотовой связи в порядке их следования. Каждая пара $(i, j)$ будет уникальной.

Выходные данные

Первые $r$ строк вывода должны содержать по $c$ целых чисел, разделенных пробелами. Число в $i$-й строке и $j$-м столбце должно быть номером ближайшей вышки сотовой связи к позиции $(i, j)$, измеренным по манхэттенскому расстоянию.

Следующие $r$ строк вывода также должны содержать по $c$ целых чисел, разделенных пробелами. Число в $i$-й строке и $j$-м столбце должно быть номером второй по близости вышки сотовой связи к позиции $(i, j)$, измеренным по манхэттенскому расстоянию.

Если для данной позиции существует несколько ближайших вышек сотовой связи, выведите ту, у которой меньше номер. Аналогично, если для данной позиции существует несколько вторых по близости вышек сотовой связи, выведите ту, у которой меньше номер.

Примеры

Входные данные 1

4 8 3
1 1
4 1
2 6

Выходные данные 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