Sudoku is a popular puzzle. It is a $9\times9$ grid filled with numbers $1\sim 9$. The player need to fill in the blanks such that:

1. Numbers in the same row are distinct;
2. Numbers in the same column are distinct;
3. Numbers in the $3\times3$ subsquares are distinct; there are 9 disjoint subsquares in total.

You can play the Soduku online here.

Input 81 integers, representing a puzzle. 0 means blank.

Output 81 integers, representing the solved puzzle. If there are multiple solutions, any one of them is ok.

Example Input

0 0 0 0 2 5 6 0 0
0 0 6 8 0 0 0 7 5
9 0 2 0 0 0 0 0 3
0 0 9 2 0 0 0 0 0
3 1 0 0 0 4 0 0 8
0 6 8 5 0 7 0 4 9
0 0 5 4 6 0 0 0 7
4 7 0 9 0 8 1 0 2
0 0 0 0 3 0 8 0 0

Example Output

7 8 4 3 2 5 6 9 1 
1 3 6 8 4 9 2 7 5 
9 5 2 1 7 6 4 8 3 
5 4 9 2 8 3 7 1 6 
3 1 7 6 9 4 5 2 8 
2 6 8 5 1 7 3 4 9 
8 2 5 4 6 1 9 3 7 
4 7 3 9 5 8 1 6 2 
6 9 1 7 3 2 8 5 4