P9382 [THUPC 2023 Finals] Freshman Dream

Little J is learning matrix multiplication. Little L tells him: as long as you multiply the elements in the same positions of two matrices, you can get the product of the two matrices. This is of course wrong, but Little L wants to keep fooling Little J. So, she needs to put a matrix multiplication problem on her own OJ such that this kind of “matrix multiplication” can also produce the correct answer. Because Little L’s OJ runs very slowly and has a very small memory limit, the answers in this matrix multiplication problem are all taken modulo $2$. Now Little L starts generating testdata. She first randomly generates an $n \times n$ matrix $A$. Specifically, each element is $1$ with probability $\frac 12$, and $0$ otherwise, and these events are independent. Now, she still needs to design another $n \times n$ $01$ matrix $B$, such that $(AB)_{ij} \equiv A_{ij} B_{ij} \pmod 2$. Little L tried generating matrices randomly, but could not find any matrix that meets the requirement; she tried constructing some matrices and found she could only construct the all-zero matrix, which is too obvious. Now she hands the task of generating testdata to you: you need to give a $B$ that meets the requirement. At the same time, to avoid making it look suspicious, she additionally requires that $B$ contains exactly $k$ ones.

Read from standard input. The first line contains two positive integers $n, k$, representing the matrix size and the $k$ in the statement. The next $n$ lines each contain $n$ integers $a_{ij}$, representing the elements of $A$.

Write to standard output. If there is no $B$ that satisfies the requirement, output one line containing one integer $-1$. Otherwise, first output one line containing one integer $1$, then output $n$ lines, each containing $n$ integers in $\{0,1\}$ to represent the elements of matrix $B$. If there are multiple possible $B$, output any one of them.

**Sample Explanation #1** Here $A$ is the identity matrix, and the constructed $B$ is also the identity matrix, so the product is also the identity matrix. At the same time, multiplying the corresponding positions also gives the identity matrix, and $B$ contains exactly $k = 3$ ones, so it satisfies the requirement. In this sample, $n$ is not $100$, but it is guaranteed that in all testdata $n$ is $100$. **Constraints** For all testdata, $n = 100$, $0 \le k \le n^2$, $a_{ij} \in \{0,1\}$, and all $a_{ij}$ are independent and uniformly random. **Source** From the finals of the 2023 Tsinghua University Student Programming Contest and Collegiate Invitational (THUPC2023). Resources such as the editorial can be found at . Translated by ChatGPT 5