数独是一种流行的报纸谜题，由一个 $9 \times 9$ 的网格组成。该网格被划分为九个 $3 \times 3$ 的“宫”。网格中的每个单元格要么是空白，要么包含一个 1 到 9 之间的数字。目标是填补空白，使得每一行、每一列和每一个宫都包含 1 到 9 的每个数字各一次。下面展示了一个谜题示例及其解法。

来源：维基共享资源

你的任务是编写一个程序来解决给定的任何数独谜题。

输入格式

输入始终包含九行，每一行代表数独谜题的一行。每一行包含九个整数，每个整数在 0 到 9 之间（含 0 和 9）。0 表示谜题中的空白单元格。保证存在一种填充该部分填充网格的方法以满足约束条件。与你在报纸上看到的谜题不同，这里的谜题是随机生成的，可能存在多个解。

输出格式

输出九行，每行包含对应数独谜题解的一行，每个单元格之间用空格分隔。如果存在多个解，你应该输出在第一个空白处填入较小数字的那个解。如果第一个空白处填入的数字相同，则选择在第二个空白处填入较小数字的解，依此类推。注意：“第一个”空白指的是最上方且最左侧的空白。因此，在上面的例子中，4 位于第一个空白处，6 位于第二个，8 位于第三个，以此类推。

样例

输入 1

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

输出 1

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