Quotdoku 是数独游戏的一种变体。与数独一样，目标是在一个 9×9 的网格中填入 1 到 9 的数字，使得每一行、每一列以及 9 个 3×3 的子网格中都恰好包含 1 到 9 的数字，同时满足特定的选择约束。

在数独中，约束条件是某些方格必须包含固定的值。在 Quotdoku 中，约束条件是对某些 3×3 子网格内相邻方格的商的限制。在每种情况下，将两个相邻值中较大的一个除以较小的一个，即可得到指定的商（忽略余数）。在下图中，分隔线上的 1 到 9 的整数表示所需的商。

编写一个程序来解决 Quotdoku 问题。

输入格式

输入的第一行包含一个十进制整数 $K$ ($0 \le K \le 81$)，表示预设值的数量。

接下来的 15 行输入由 0 到 9 的值组成，以空格分隔。值为 0 表示对应的一对数值没有约束。否则，输入值给出了商的约束。第 1、3、5、6、8、10、11、13 和 15 行包含 6 个值，对应于符号左右两侧数值相除的商的约束。第 2、4、7、9、12 和 14 行包含 9 个值，对应于符号上下两侧数值相除的商的约束。

接下来的 $K$ 行输入，每行包含三个 1 到 9 之间的十进制整数，以空格分隔。这些值依次给出了每个预设值的行、列和数值。

输出格式

你的程序应输出 9 行，每行包含 9 个以空格分隔的十进制数字。9 行输出中第 $i$ 行的第 $j$ 个位置的值即为第 $i$ 行第 $j$ 列的解。

样例

样例输入 1

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

样例输出 1

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

样例输入 2

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

样例输出 2

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