题目内容

这是一种靠逻辑把空位补全的古典益智。源头可追溯到十八世纪，瑞士人当时研究的是拉丁方；这套玩法后来传入日本，名称才固定下来。

九阶正方形上，每一条横行、每一条竖列，以及每一个三乘三的小宫（一共九个），都要正好放入 $1$ 到 $9$，彼此不能一样。

补全之后，上面三条同时成立。

名叫超级数独的加强版本，不再把阶数锁死在九。边长可以取 $4$、$9$、$16$，也可以取某个正整数 $t$ 的平方，盘面即 $(t^2)\times(t^2)$，比这再大的阶也沿用同一套规则。

请编写程序，自动把盘面上的空位补成一组合法结果。

输入描述

首行给出盘面边长，取值只可能是 $4$、$9$、$16$。例如首行写 $9$，就说明后面紧跟一张九乘九的方阵。随后的行数与边长相同，每一行含有同样多个整数，彼此以空格隔开。整数 $0$ 代表该格仍空着，其余整数都在 $1$ 与边长之间。格式如下：

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

输出描述

把填好的方阵逐行写出，同一行的整数以空格隔开，原来空着的格子都换成符合规则的数。例如：

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

合法补法只要多于一组，就只写 $0$；一种都凑不出来时，同样只写 $0$。

样例1

输入

4
2 1 4 0
3 0 1 2
1 3 0 4
0 2 3 1

输出

2 1 4 3
3 4 1 2
1 3 2 4
4 2 3 1

说明

四个空位都被唯一确定，整张方阵只有这一组补法。

样例2

输入

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

输出

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

说明

空格均已按横行、竖列与小宫的规则补上，不存在另一组合法结果。