Route

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

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

Output

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