Задача №619. Маршрут

В таблице из \(N\) строк и \(N\) столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (\(N\), \(N\)), чтобы сумма цифр в клетках, через которые он пролегает, была минимальной; из любой клетки ходить можно только вниз или вправо.

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

В первой строке находится число \(N\). В следующих \(N\) строках содержатся по \(N\) цифр без пробелов. 2 <= \(N\) <= 250.

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

Выводятся \(N\) строк по \(N\) символов. Символ решётка показывает, что маршрут проходит через эту клетку, а минус - что не проходит. Если путей с минимальной суммой цифр несколько, вывести любой.

Примеры
Входные данные
2
00
00
Выходные данные
#-
##
Входные данные
2
00
90
Выходные данные
##
-#
Сдать: для сдачи задач необходимо войти в систему