Background

数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。

现在请你编写程序对一个数独进行求解

Input

9*9的数字矩阵，1~9表示对应位置上已给定的数字，0表示需要你补充的数字

Output

输出9行9列的补充完整后的数独情况，输出所有情况，每种情况之间隔一行

Samples

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

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

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