Marşurut

N sətir və N sütundan ibarət cədvəlin xanaları 0-9 diapazonunda rəqəmlərlə doldurulmuşdur. (1, 1) xanasından (N, N) xanasına gedən elə yol tapmaq lazımdır ki, keçilən xanalardakı rəqəmlərin cəmi minimal olsun. İstənilən xanadan yalnız aşağıya və ya sağa hərəkət etmək olar.

Giriş verilənləri

İlk sətirdə N (2 ≤ N ≤ 250) ədədi verilir. Növbəti N sətrin hər birində boşluq olmadan N rəqəm verilir.

Çıxış verilənləri

Hər birində N simvol olan N sətir verməli. # işarəsi marşurutun bu xanadan keçdiyini ifadə edir, nöqtə isə keçmədiyini bildirir. Əgər rəqəmlərin cəmi minimal olan bir neçə yol olarsa, onlardan istənilən birini verməli.

Nümunələr