In the table of \textbf{N} rows and \textbf{N} columns of cells filled with numbers from \textbf{0} to \textbf{9}. Need to find a way out of the cell (\textbf{1}, \textbf{1}) into the cell (\textbf{N}, \textbf{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. \InputFile In the first line is the number of \textbf{N} (\textbf{2} ≤ \textbf{N} ≤ \textbf{250}). In the next \textbf{N} lines contains the \textbf{N} digits without spaces. \OutputFile The output is \textbf{N} rows by \textbf{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.