Description

Due to the popularity of The Hobbit, L’s roommate X has recently become interested in the currency they use. For this study, X needs to understand something called a bit matrix. Although a bit matrix is still a matrix, its multiplication is a little different from ordinary matrix multiplication.

For bit matrices, $C = A \times B$ means $c_{i, j} = V_{k=1}^{n} a_{i k} \bigoplus b_{k j}$. Here $V$ denotes taking bitwise OR over a sequence; for example, $V_{i=1}^{n} i$ means $1 \mid 2 \mid \cdots \mid n$. The symbol $\mid$ means bitwise OR. Bitwise OR views two numbers in binary: if at bit $i$ at least one of the two numbers is $1$, then the $i$-th bit of the result is $1$; otherwise that bit is $0$. The symbol $\bigoplus$ denotes bitwise XOR: if the $i$-th bits of two binary numbers are different, then the $i$-th bit of the result is $1$; otherwise it is $0$.

Here is an example of bit-matrix multiplication.

$$\begin{bmatrix}1&6\\3&5\end{bmatrix}\times\begin{bmatrix}3&6\\5&7\end{bmatrix}=\begin{bmatrix}3&7\\0&7\end{bmatrix}$$

Now X would like you to compute $A^{m}$, where $A$ is an $n \times n$ bit matrix, and $A^{m}$ is the result of multiplying $m$ copies of $A$. Precisely:

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

Input Format

The first line contains two positive integers $n, m$. The next $n$ lines each contain $n$ non-negative integers; in these $n$ lines, the $j$-th number of the $i$-th line is the element $a_{i, j}$ of the bit matrix.

Output Format

Output the bit matrix $A^{m}$. That is, print a bit matrix in the same format as the input matrix $A$. See the sample output for details.

2 4
10 5
5 10

0 15
15 0

3 16
6 5 7
5 6 7
7 7 6

0 3 3
3 0 3
3 3 0

Hint

Constraints

• For $10\%$ of the testdata, $n \le 4$, $m \le 10000$.
• For $30\%$ of the testdata, $n \le 10$, $m \le 10^9$.
• For $100\%$ of the testdata, $n \le 500$, $m \le 10^9$, and all input integers do not exceed $10^9$.

Translated by ChatGPT 5