Problem Description

Kitty has \( n^2 \) lights arranged in an \( n \times n \) matrix.

One day, Kitty noticed that some of these lights were on, and some were off. She wants to turn them all off.

To achieve her goal, Kitty can perform three types of operations:

• (1) Choose a row and reverse the state of all lights in this row. This means if a light in this row is on, after this operation, it is now off. If a light in this row is off, after this operation, it is now on.

• (2) Choose a column and reverse the state of all lights in this column. This means if a light in this column is on, after this operation, it is now off. If a light in this column is off, after this operation, it is now on.

• (3) Choose exactly one light and reverse its state. This operation can only be performed not more than \( k \) times.

For the current state, help Kitty achieve her goal within \( 3n \) operations.

Input Format

The first line contains two integers \( n \) (\( 1 \leq n \leq 1000 \)) and \( k \) (\( 0 \leq k < n \)), as described above.

Then \( n \) lines follow, each containing exactly \( n \) numbers. \( 0 \) represents that the light is off at this time, while \( 1 \) represents the opposite.

The \( y \)-th number of the \( (x+1) \)-th line in the input represents the light at coordinate \( (x, y) \).

Output Format

If Kitty cannot achieve her goal, print \(-1\) in a single line.

Otherwise, print \( M \) (\( 0 \leq M \leq 3n \)) in the first line, indicating the number of operations she needs to perform.

The next \( M \) lines, each containing \( 2 \) integers \( x, y \), separated by whitespace.

If \( 1 \leq x \leq n \) and \( 1 \leq y \leq n \), it means Kitty will reverse the light at coordinate \( (x, y) \).

If \( x = 0 \) and \( 1 \leq y \leq n \), it means Kitty will reverse all lights at coordinates \( (z, y) \) where \( 1 \leq z \leq n \).

If \( 1 \leq x \leq n \) and \( y = 0 \), it means Kitty will reverse all lights at coordinates \( (x, z) \) where \( 1 \leq z \leq n \).

If there are multiple answers, print any of them.

Sample Input and Output

Sample Input #1

2 0
0 1
1 0

Sample Output #1

2
0 2
2 0

Sample Input #2

3 1
1 0 0
0 1 0
0 0 1

Sample Output #2

-1

见题面 Input 部分

见题面 Output 部分