eolymp
bolt
Try our new interface for solving problems

Route

Time limit 1 second
Memory limit 64 MiB

In the table of N rows and N columns of cells filled with numbers from 0 to 9. Need to find a way out of the cell (1, 1) into the cell (N, N), the sum of the numbers in the cells, through which it passes, to a minimum of every cell can only go down or right.

Input data

In the first line is the number of N (2N250). In the next N lines contains the N digits without spaces.

Output data

The output is N rows by N characters. Pound symbol indicates that the route passes through the cage, and the point-that does not pass. If the paths with minimum sum of digits of a few, to withdraw any.

Examples

Input example #1
3
943
216
091
Output example #1
#..
###
..#