描述

数独是源自18世纪瑞士的一种数学游戏（一说起源于日本）。起初是一种运用纸、笔进行演算的。玩家需要根据正方形格子上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个小格子内的数字不重复。

例如，下面是个4x4的数独题面，可以填入格子的数字范围是1～4。要求填满数字之后，每一行的4个数字没有重复，每一列的4个数字没有重复，四个2x2的方格内的4个数字也没有重复。

这个数独的答案如下

现在要求编程求出给定数独的答案。

输入输出格式

输入

四行，每一行四个字符，对应数独题面的每一行。其中的空格用符号*代表。每个题面都保证有且仅有一个解答。

输出

四行，每一行四个数字，对应数独题解的每一行。

样例

*2*1
****
****
3*2*

4231
1342
2413
3124