Маршрут

У таблиці з N рядків і N стовбців клітинки заповнені цифрами від 0 до 9. Потрібно знайти такий шлях з клітинки (1, 1) у клітинку (N, N), щоб сума цифр у клітинках, через які він проходить, був мінімальним; з довільної клітинки ходити можна лише вниз або праворуч.

Вхідні дані

У першому рядку знаходиться число N (2 ≤ N ≤ 250). У наступних N рядках міститься по N цифр без пропусків.

Вихідні дані

Виводиться N рядків по N символів. Символ решітка показує, що маршрут проходить через цю клітинку, а точка - що не проходить. Якщо шляхів з мінімальною сумою цифр декілька, вивести довільний.

Приклади