Little J is learning about matrix multiplication. Little L, who is nearby, tells him: "You can just multiply the corresponding positions of two matrices to get their product."

This is, of course, incorrect, but Little L wants to continue tricking Little J. To do this, she needs to put a matrix multiplication problem on her OJ such that this kind of "matrix multiplication" also yields the correct answer.

Since Little L's OJ runs very slowly and has very tight memory limits, the answers to this matrix multiplication problem are all in the sense of $\pmod 2$.

Now, Little L starts creating the data. She first randomly generates an $n \times n$ matrix $A$. Specifically, each element is $1$ with probability $\frac{1}{2}$ and $0$ with the remaining probability, and these events are mutually independent. Now, she also needs to design another $n \times n$ $01$-matrix $B$ such that $(AB)_{ij} \equiv A_{ij}B_{ij} \pmod 2$.

Little L tried to generate the matrix randomly, but could not find any matrix that met the requirements; she tried to construct a few matrices, but found she could only construct the all-zero matrix, which is too obvious. Now, she has handed the task of generating the data to you. You need to provide a $B$ that satisfies the requirements, and to prevent others from seeing that the data is rigged, she also requires that $B$ contains exactly $k$ ones.

Input

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

Output

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

Examples

Input 1

3 3
1 0 0
0 1 0
0 0 1

Output 1

1
1 0 0
0 1 0
0 0 1

Note 1

Here $A$ is the identity matrix, and the constructed $B$ is also the identity matrix; their product is also the identity matrix. At the same time, multiplying the corresponding positions also results in the identity matrix, and $B$ contains exactly $k = 3$ ones, so it satisfies the requirements. In this example, $n$ is not $100$, but it is guaranteed that in all test data, $n = 100$.

Subtasks

For all test data, $n = 100$, $0 \le k \le n^2$, $a_{ij} \in \{0, 1\}$, and all $a_{ij}$ are independent and uniformly random.