В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N), чтобы сумма цифр в клетках, через которые он пролегает, была минимальной; из любой клетки ходить можно только вниз или вправо.
Входные данные
В первой строке находится число N. В следующих N строках содержатся по N цифр без пробелов. 2 <= N <= 250.
Выходные данные
Выводятся N строк по N символов. Символ решётка показывает, что маршрут проходит через эту клетку, а минус - что не проходит. Если путей с минимальной суммой цифр несколько, вывести любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
00
00
|
#-
##
|
|
2
|
2
00
90
|
##
-#
|