题目描述

Kitty has $n^2$ lights, which form an $n\times n$ matrix.

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

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

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

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

• (3) Choose exactly one light, reverse the state of this light. This operation can only be performed not more than $k$ times.

For the current state, help Kitty achieve her goal within $3n$ operations.

输入格式

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

Then $n$ lines follow, each line has exactly $n$ numbers, $0$ represents that the light is turned off at this time, while $1$ represents the opposite.

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

输出格式

If Kitty can not 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 line contains $2$ integers $x,y$, separated by white space.

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

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

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

If there are multiple answers, print any of them.

2 0
0 1
1 0

2
0 2
2 0

3 1
1 0 0
0 1 0
0 0 1

-1