Neighbors Puzzle 基于这样一个概念：如果两个整数的差为 1，则它们是“邻居”。该谜题由一个 $N$ 行 $N$ 列的网格组成。在某些内部边上标有菱形。此外，会有少量预先指定的数值（例如，第 2 行第 7 列的 7）。

要解决这个谜题，请在空白方格中填入 1 到 $N$ 之间的整数，使得：

• 每一行中，1 到 $N$ 的每个数字恰好出现一次。
• 每一列中，1 到 $N$ 的每个数字恰好出现一次。
• 如果两个数值之间有菱形，则它们是邻居（差为 1）。
• 如果两个数值之间没有菱形，则它们不是邻居（差值大于 1）。

输入格式

输入的第一行包含两个以空格分隔的十进制整数 $N$ ($4 \le N \le 12$)，表示行数和列数；以及 $K$ ($(N/2) + (N*N)/16 \le K \le N*N$)，表示预先指定数值的数量。

接下来的 $(2N-1)$ 行输入由 0 或 1 组成，分别表示“不是邻居”或“是邻居”，中间没有空格。

该集合中奇数编号的行包含 $(N-1)$ 个值，对应于方格内垂直线两侧数值的约束。

偶数编号的行包含 $N$ 个值，对应于符号上方和下方数值的约束。

这 $(2N-1)$ 行之后是 $K$ 行，每行包含三个以空格分隔的十进制整数。这些值依次给出了每个预先指定数值的行、列和数值（均为 $1 \dots N$）。

输入数据保证能生成唯一的谜题解。

输出格式

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

样例

输入格式 1

7 6
100000
0111010
100000
0000000
001001
0010010
000000
0000000
000000
0000000
001000
0001010
000001
2 7 7
6 1 2
3 3 2
7 6 2
5 3 6
4 7 6

输出格式 1

4 3 5 7 1 6 2
1 2 4 6 3 5 7
7 5 2 1 6 3 4
3 7 1 5 2 4 6
5 1 6 2 4 7 3
2 6 3 4 7 1 5
6 4 7 3 5 2 1