Bit Matrix Exponentiation

In this problem, you are given an n×n bit matrix A and a positive integer m. The multiplication of two bit matrices is defined differently from the usual matrix multiplication. Specifically, if C = A × B, then each element of C is computed as:

$$c_{i,j}=\bigvee_{k=1}^{n}\Big(a_{i,k}\oplus b_{k,j}\Big)$$

Here, \(\bigvee\) denotes the bitwise OR applied over the sequence, and \(\oplus\) denotes the bitwise XOR operation. In other words, for each element \(c_{i,j}\), you compute \(a_{i,k}\oplus b_{k,j}\) for every \(k\) from 1 to n, and then take the bitwise OR of all these values.

For example, given two matrices

$$A=\begin{bmatrix}1&6\\3&5\end{bmatrix}, \quad B=\begin{bmatrix}3&6\\5&7\end{bmatrix},$$

we have:

$$A\times B=\begin{bmatrix}(1\oplus3)\vee(6\oplus5) & (1\oplus6)\vee(6\oplus7)\\ (3\oplus3)\vee(5\oplus5)& (3\oplus6)\vee(5\oplus7)\end{bmatrix}=\begin{bmatrix}3&7\\0&7\end{bmatrix}.$$

Your task is to compute \(A^m\) which is defined as the bit matrix A multiplied by itself m times. Formally,

• \(A^1 = A\),
• \(A^m = A^{m-1}\times A\) for \(m > 1\).

Note that there is no multiplicative identity matrix for this operation, so you should implement the exponentiation using a recursive or iterative method that does not rely on an identity element (for example, by using divide and conquer, where \(A^m = (A^{\lfloor m/2 \rfloor}\times A^{\lfloor m/2 \rfloor})\) and, if m is odd, multiplying by A one extra time).

inputFormat

The first line contains two integers n and m, where n is the size of the square matrix and m is the power to which the matrix is raised. Then follow n lines, each containing n integers representing the matrix A.

outputFormat

Output the resulting n×n matrix \(A^m\). Each of the n lines should contain n integers separated by spaces.

sample

2 2
1 6
3 5

5 7
6 5