Description

数独是一个非常简单的任务。

一个9行9列的正方形表被分成9个较小的3x3，如图所示。

!

在一些单元格中，从1写到9的十进制数字。其他细胞是空的。

目标是用从1到9的十进制数字填充空单元格，每个单元格有一个数字，

这样在每一行、每列和每个标记为3x3的子方格中，将出现从1到9的所有数字。

Format

Input

有9行，对应于表的行。 在每一行上都会给出一个精确的9位小数字符串，对应于这一行中的单元格。 如果单元格为空，则由0表示。输出量

Output

对于每个测试用例，您的程序应该以与输入数据相同的格式打印解决方案。空的单元格必须按照规则填充。

如果解决方案不是唯一的，输出字典序最小的一个，即保证第1行第1个数字尽可能小，如果这个数字是一样的，则保证第1行第2个数字尽可能小......

Samples

103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127