说明

编写一个程序，通过填充空格来解决数独问题。 数独的解法需 遵循如下规则：

• 数字 $1\sim9$ 在每一行只能出现一次；
• 数字 $1\sim9$ 在每一列只能出现一次；
• 数字 $1\sim9$ 在每一个以粗实线分隔的 $3\times3$ 宫格内只能出现一次。（请参考样例说明）

数独部分空格内已填入了数字，空白格用 . 表示。

输入

共 $9$ 行字符串； 每行 $9$ 个字符； 空白格用 . 表示。

输出

数独的答案，也是 $9$ 行，每行 $9$ 个数字。

样例

53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79

534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

提示

样例说明

解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

数据范围

• 题目数据 保证 输入数独仅有一个解。