Henry 在“某某国立搜索大学”的一堂枯燥的高等数学课上睡觉。当他突然醒来时，老师要求他解决以下问题：给定一个 $n \times n$ 的整数矩阵 $A$，Henry 必须找到可逆整数矩阵 $L$ 和 $R$，使得满足以下条件：

• $B = LAR$ 是一个对角矩阵；
• 存在某个 $j$ ($0 \le j \le n$)，使得 $b_{i,i} = 0$ 当且仅当 $i > j$；
• 对于所有从 $2$ 到 $j$ 的 $i$，数字 $b_{i,i}$ 都能被 $b_{i-1,i-1}$ 整除。

如果存在一个整数矩阵 $C^{-1}$ 使得 $CC^{-1} = I$（其中 $I$ 是单位矩阵），则称整数矩阵 $C$ 是可逆的。

Henry 大部分课都在睡觉，所以他不知道怎么做。因此他请求你的帮助。

输入格式

输入文件包含多个测试用例。 每个测试用例以一个整数 $n$ 开始，表示矩阵的大小，随后是 $n$ 行，每行包含 $n$ 个整数，即给定的矩阵（$2 \le n \le 5$，矩阵元素在 $-10$ 到 $10$ 之间）。 输入以一行 $n = 0$ 结束。每个输入文件最多包含 $100$ 个测试用例。

输出格式

对于每个测试用例，打印四个整数矩阵：$L$、$L^{-1}$、$R$ 和 $R^{-1}$。保证此类矩阵总是存在。矩阵之间用空行分隔。如果有多种解，打印任意一种即可。

样例

输入 1

3
1 2 3
6 5 4
7 8 9
0

输出 1

1 0 0
1 1 -1
-13 -6 7

1 0 0
-6 1 1
-7 6 1

1 -2 1
0 1 -2
0 0 1

1 2 3
0 1 2
0 0 1

说明

在给定的示例中：

$$\begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & -1 \\ -13 & -6 & 7 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 \\ 6 & 5 & 4 \\ 7 & 8 & 9 \end{pmatrix} \begin{pmatrix} 1 & -2 & 1 \\ 0 & 1 & -2 \\ 0 & 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 0 \end{pmatrix}$$