Problem Description

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.

Input Format

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$.

Output Format

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.

3 3
1 0 0
0 1 0
0 0 1

1
1 0 0
0 1 0
0 0 1

Hint

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 https://github.com/THUSAAC/THUPC2023.

Translated by ChatGPT 5