测试数据来自 system/1632

背景

通过了Snowy的考验，新一在Snowy的帮助下来到了另一个房间的门前。他推开门，顿时被眼前的景象惊呆了......
整个房间四壁围满了电脑屏幕，从无数个方向投出诡异的白光，洒在房间中央的人身上。那人缓缓转身：“你好，我是Rum。”
“你......hhdllhflower!”
Rum没有理会新一的话，目光绕着房间四周转了一圈：“看到了吧？这些堪称六合间最高深的智力游戏——梦幻数独。你如果能把它们解出来，我便可以告诉你小兰的下落。否则，我就要你在这里陪我，直到这些数独全都解出来为止!”
“梦幻数独？有什么特殊规则么？”新一怀疑地问道。

“没有，只不过难一些而已。”
“......”

描述

新一的时间已经不多了，为了尽快找回小兰，他决定拜托你——阿笠博士的编程顾问——编一个程序解决这些数独。

数独介绍：

单元格：数独中最小的单元，标准数独中共有81个；
行：横向9个单元格的集合；
列：纵向9个单元格的集合；
宫：标准数独中为3×3的9个单元格的集合，在数独中为左上，正上，右上，左，中，右，左下，正下，右下分布；
已知数：数独初始盘面给出的数字；
候选数：每个空单元格中可以填入的数字。

规则：
数独每行、每列及每宫填入数字1-9且不能重复。

如若仍然不明白规则，请参照vijos P1345

格式

输入格式

一个9*9的方阵，即初始数独。

如果某数字为0表示此处为空。否则为已知1-9之间的整数。

输出格式

一个9*9的方阵，即完成的数独。完成的数独应该符合规则且没有0。

样例1

样例输入1

000000016
000500040
300070000
900000200
000408000
700600000
000023700
040000000
010000000

样例输出1

475239816
892561347
361874925
954317268
126498573
738652491
689123754
547986132
213745689