CBR发明了一种独特的加密算法，并把它应用在了他的网站里。为了检验这套算法是否真的安全，你决定尝试破解它。
虽然CBR的前端写得混乱不堪还没有注释，但经过几十分钟的不懈努力，你终于看明白了加密算法的流程。关键步骤概括如下：
被加密的明文是 $$$m$$$ 个二维向量 $$$T_0,T_1,\cdots,T_{m-1}$$$，加密密钥是 $$$n$$$ 个 $$$2\times2$$$ 的矩阵 $$$A_0,A_1,\cdots,A_{n-1}$$$。加密时，首先生成加密密钥 $$$A_i=b_iG^{a_i}$$$，其中 $$$a_i$$$ 和 $$$b_i$$$ 是任意两个整数，$$$G=\begin{pmatrix}1&3\\-4&-5\end{pmatrix}$$$，然后对于所有 $$$k=0,\cdots,m-1$$$，计算 $$$$$$ S_k=\sum_{i+j=k}A_iT_{j} $$$$$$ 所得 $$$S_0,S_1,\cdots,S_{m-1}$$$ 即为密文。
同时，你发现解密过程和加密过程很类似。解密密钥是 $$$m$$$ 个 $$$2\times2$$$ 的矩阵 $$$B_0,B_1,\cdots,B_{m-1}$$$。解密时，对于所有 $$$k=0,\cdots,m-1$$$，计算 $$$$$$ T_k=\sum_{i+j=k}B_iS_{j} $$$$$$ 所得 $$$T_0,T_1,\cdots,T_{m-1}$$$ 即为原始明文。
所有运算在模素数 $$$p=931135487$$$ 下进行。
现在，你有一些加密密钥，你要算出它们对应的解密密钥。因为CBR没有在前端实现解密算法，所以你决定自己动手。
第一行是一个正整数 $$$T\ (T\le5)$$$，代表测试数据的组数；
接下来是 $$$T$$$ 组数据，每组数据中：
第一行包含两个正整数 $$$n,m\ (n,m\le10^5)$$$，意义如上所述；
接下来 $$$n$$$ 行，第 $$$i+1$$$ 行包含 $$$4$$$ 个 $$$[0,p)$$$ 内的整数 $$$A_{i,1,1},\ A_{i,1,2},\ A_{i,2,1},\ A_{i,2,2}$$$，代表 $$$A_i$$$ 的 $$$4$$$ 个元素。数据保证有解。
对于每组数据：输出 $$$m$$$ 行，第 $$$i+1$$$ 行包含 $$$4$$$ 个 $$$[0,p)$$$ 内的整数 $$$B_{i,1,1},\ B_{i,1,2},\ B_{i,2,1},\ B_{i,2,2}$$$，代表$$$B_{i}$$$的$$$4$$$个元素。
2 2 2 1 0 0 1 1 3 931135483 931135482 2 3 765802924 214928128 334186154 335946668 459485228 792738722 184529020 736278758
1 0 0 1 931135486 931135484 4 5 330942419 845502507 734934298 502208379 811063786 267667172 884624420 275729442 751187425 100246669 487094766 550694087
