數獨一般由 $n$ 個 $\sqrt{n} \times \sqrt{n}$ 的 $n$ 宮格組成。
每一直行和每一橫列的數字均須包含 $1\sim n$，不能缺少，也不能重複。每一宮（粗黑線圍起來的區域，通常是 $\sqrt{n} \times \sqrt{n}$ 的 $n$ 宮格）的數字均須包含 $1\sim n$，不能缺少，也不能重複。完成需同時滿足這三個條件。
如圖是一個 $n$ 宮格（$n=9$）數獨的示例。
給定一個不完整的數獨題面，要求補上任意數量的數字，使得補完以後的數獨恰好有兩個解，即有唯二解；且要求在所有這樣的補法中，它所對應的唯二解差異最大。這裡，差異定義為將兩個解法逐單元格比對，不一樣的數字個數。
同時，對於數獨中的任意兩個位置，設 $x_1,x_2$ 表示兩個唯二解在兩個數獨中第一個位置的數，$y_1,y_2$ 表示兩個唯二解在兩個數獨中第二個位置的數，不同時滿足 $x_1\not=x_2,y_1\not=y_2,x_1\not=y_2,x_1 \not = y_1$。
輸入格式
第一行，一個數 $n$ 表示數獨大小。
接下來 $n$ 行，每行 $n$ 個數 $a_{i,j}$，表示一個不完整的數獨題面，填數字 $0$ 的位置表示那裡沒有數字。
輸出格式
$n$ 行，每行各 $n$ 個數，輸出補完以後的盤面，若有多種補法都可以滿足其對應的唯二解差異在所有補法中最大，輸出任意一種即可。
範例
輸入格式 1
4 3 0 0 0 0 0 0 0 0 3 0 0 0 0 0 3
輸出格式 1
3 0 0 0 0 0 0 2 0 3 0 0 2 0 0 3
說明
範例輸出所對應的唯二解是：
3 2 1 4 1 4 3 2 4 3 2 1 2 1 4 3
和：
3 2 4 1 4 1 3 2 1 3 2 4 2 4 1 3
逐一比對可得差異為 $8$，可以證明，這是其中一種使得差異達到這個題面的最大值 $8$ 的方法。
輸入格式 2
16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
輸出格式 2
(output data for test case 14)
輸入格式 3
16 0 0 10 0 0 0 0 1 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 7 0 0 7 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 0 8 0 0 0 12 11
輸出格式 3
(output data for test case 15)
資料範圍
| 子任務編號 | 資料點編號 | 分值 | 資料範圍 | 額外限制 |
|---|---|---|---|---|
| 1 | 1 | 8 | $n=4$ | 無 |
| 1 | 11 | 8 | $n=4$ | 無 |
| 1 | 12 | 8 | $n=4$ | 無 |
| 1 | 13 | 8 | $n=4$ | 無 |
| 2 | 2 | 6 | $n=9$ | 初始給定數字數量為 $0$ |
| 2 | 3 | 6 | $n=9$ | 保證盤面至多給出 $11$ 個不為 $0$ 的數 |
| 2 | 4 | 6 | $n=9$ | 保證盤面至多給出 $11$ 個不為 $0$ 的數 |
| 2 | 5 | 6 | $n=9$ | 保證盤面至多給出 $11$ 個不為 $0$ 的數 |
| 2 | 6 | 6 | $n=9$ | 保證盤面至多給出 $11$ 個不為 $0$ 的數 |
| 2 | 7 | 6 | $n=9$ | 保證盤面至多給出 $11$ 個不為 $0$ 的數 |
| 2 | 8 | 6 | $n=9$ | 保證盤面至多給出 $11$ 個不為 $0$ 的數 |
| 2 | 9 | 6 | $n=9$ | 保證盤面至多給出 $11$ 個不為 $0$ 的數 |
| 2 | 10 | 6 | $n=9$ | 保證盤面至多給出 $11$ 個不為 $0$ 的數 |
| 3 | 14 | 7 | $n=16$ | 初始給定數字數量為 $0$ |
| 4 | 15 | 7 | $n=16$ | 保證盤面至多給出 $20$ 個不為 $0$ 的數 |
其中子任務 1 的時間限制為 2s。其他的時間限制為 30s。
對於所有資料：$a_{i,j} \in [0,n]$，保證給出的不完整數獨題面至少存在一種補法使得其有唯二解。
注意：表格在暗色主題下邊框顯示不清晰，如果需要可以調成亮色主題。