Mod 2 Matrix Multiplication Trick

Little J is learning matrix multiplication. Little L, sitting beside him, tells him that to multiply two matrices, you only need to multiply their corresponding entries element‐wise. Although this is obviously wrong, Little L wants to trick Little J by putting a problem on her online judge where this "matrix multiplication" produces the correct answer.

To achieve this, all answers are computed under modulo $$2$$ arithmetic. Little L generates an $$n\times n$$ matrix $$A$$ at random, where each element is independently set to $$1$$ with probability $$\frac{1}{2}$$ and $$0$$ otherwise. She now needs you to design another $$n\times n$$ binary (i.e. $$0$$ or $$1$$) matrix $$B$$ such that

$$(AB)_{ij} \equiv A_{ij}\,B_{ij} \pmod{2}, \quad \text{for all } 1\le i,j\le n. $$

To avoid suspicion, the matrix $$B$$ must contain exactly $$k$$ ones. Note that the usual matrix product is defined as $$ (AB)_{ij}=\sum_{r=1}^n A_{ir}B_{rj}\ (\text{computed modulo }2). $$

Observation: With modulo $$2$$ arithmetic and the random matrix $$A$$, it turns out that for almost every column the only safe choices for the entries in $$B$$ are on the diagonal. In fact, one can prove that if we set all off-diagonal entries of $$B$$ to $$0$$, then the given condition reduces to verifying that for every diagonal position $$i$$ for which $$B_{ii}=1$$, it holds that $$A_{ii}=0$$.

Your task is to output a matrix $$B$$ that meets the above condition and contains exactly $$k$$ ones. It is guaranteed that there is a valid solution for the given input.

inputFormat

The first line contains two integers $$n$$ and $$k$$, where $$1 \le n \le 500$$ and $$0 \le k \le n$$ (it is guaranteed that a solution exists).

Each of the next $$n$$ lines contains $$n$$ integers (either $$0$$ or $$1$$), representing the matrix $$A$$. The $$j$$-th number in the $$i$$-th line is $$A_{ij}$$.

outputFormat

Output the matrix $$B$$ in the same format as the input: $$n$$ lines, each containing $$n$$ integers (either $$0$$ or $$1$$). The matrix $$B$$ should have exactly $$k$$ entries equal to $$1$$ and must satisfy $$\forall\,1\le i,j\le n,\; (AB)_{ij} \equiv A_{ij}\,B_{ij} \pmod{2}.$$

sample

3 1
0 1 0
1 1 0
0 0 1

1 0 0
0 0 0
0 0 0