Алиса часто играет в шахматы. Причем так как она любит путешествовать по другим галактикам, она знает много разновидностей этой древней игры. Иногда она просто решает головоломки, созданные на шахматной доске. Шахматная доска Алисы может иметь самые разные размеры, не только 8×8.
Сейчас Алиса решает следущую шахматную головоломку, суть которой заключается в следующем. На одно из полей доски размером m×n записывается некоторое положительное целое число и затем на него ставится ферзь. После этого ферзь делает k ходов. Ходит ферзь по стандартным шахматным правилам. Ферзь не может ходить на поля, на которых уже был. Также, перед там как выполнить ход, на выбранном поле пишется целое число, причем такое, что оно больше всех других чисел, уже записанных на доске.
Решение головоломки заключается в том, чтобы восстановить маршрут ферзя по числам, записанным на доске. Возможно записанные числа не дают решения.
Для решения этой головоломки Алиса написала программу, которая может быстро ее решать при больших значениях m, n и k.
Напишите и вы такую программу.
В стандартных шахматных правилах ферзь может переместиться на любое поле доски, находящееся на одной вертикали, горизонтали или диагонали с тем полем, на котором он находится.
Входные данные
В первой строке вводятся числа
m,
n и
k ( 1< = m, n <= 300, 0 <= k < mn). Следующие
m строк содержат по
k целых чисел и описывают поля доски (пустому полю соответствует число
0, а полю, на котором записано число – это число). Все числа, записанные на доске, положительные, целые и не превышают 10
9.
Выходные данные
Если головоломка составлена с ошибкой и записанные на ней числа не дают решения, то вывелите «
Wrong Board».
В противном случае выведите
m строк по
n чисел – для каждого поля выведите номер хода, перед которым ферзь побывал на этом поле, а для последнего поля, на котором он оказался – число
k + 1. Для полей, на которые ферзь не попадал, выведите число
0.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4 4 7
10 20 0 100
30 0 0 40
0 0 0 0
45 42 0 70
|
1 2 0 8
3 0 0 4
0 0 0 0
6 5 0 7
|
| 2 |
2 4 4
10 20 30 40
0 50 0 0
|
Wrong Board
|
| 3 |
2 2 2
1 2
4 3
|
Wrong Board
|