#26. 宫殿大门

宫殿大门

题目描述

密码箱终于被打开了,里面真的有一张古代的藏宝图,这是一个古代君主留下来的宝藏,藏在一个至今没有人发现的地下宫殿中,要取得宝藏必须破解重重机关。小可可毫无畏惧,作为他的好朋友,你们就这样开始了寻宝旅程。经过千辛万苦,你们来到了地下宫殿的入口,遇到了第一个麻烦。宫殿的大门怎么都无法打开。小可可仔细观察以后发现,大门的左半扇门上有一些数字,像一个 n×nn\times n 的矩阵般排列,右半扇门对应的位置上也有同样的 n×nn\times n 数字排列,不过数字均为 00,这些 00 都可以通过机关变成其他的数字,甚至是负数,但是排列方式不会变。

小可可仔细研究了藏宝图,发现要打开这扇门必须要将右半扇门上的数字按照一定的规律进行改变。若假设左边 n×nn\times n 矩阵为 AA,改变后的右边 n×nn\times n 矩阵为 BB,这个规律就是,矩阵 A,BA,B 的乘积 CC 矩阵满足 Ci,j=k=1nai,k×bk,jC_{i,j}=\sum_{k=1}^n a_{i,k}\times b_{k,j},且 C=A×B=EnC=A\times B=E_n

其中,EnE_n 为:

  • i=ji=jEi,j=1E_{i,j}=1
  • 否则,Ei,j=0E_{i,j}=0

即:BBAA 的逆矩阵。

你能帮助小可可打开这扇门吗?

输入格式

输入文件的第一行为一个整数 nn
以下 nn 行,每行 nn 个数,按照行主序给出 AA 的每个元素,即:
A1,1,A1,2,,A1,n,A_{1,1}, A_{1,2},\dots ,A_{1,n},
A2,1,A2,2,,A2,n,A_{2,1}, A_{2,2},\dots ,A_{2,n},
\dots
An,1,An,2,,An,nA_{n,1}, A_{n,2}, \dots,A_{n,n}

输出格式

输出文件为 nn 行,每行 nn 个整数,且在 2×109-2\times 10^92×1092\times 10^9 之间,每两个相邻的数用一个空格隔开,即按照行主序表示的矩阵 BB
输入数据保证这个矩阵 BB 存在,且 BB 的每个元素为一个整数,并且在 2×109-2\times 10^92×1092\times 10^9 之间。

特别提示:由于测试采取文件比对方式,所以这里约定,如果结果中某个数为 00,则应输出 0,而不是 -0

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

数据规模与约定

对于 100%100\% 的数据,1n2001\le n\le 2002×109Ai,j,Bi,j2×109-2\times 10^9\le A_{i,j},B_{i,j}\le 2\times 10^9