Limits 1s, 512 MB

You are at a 12 story building called ECE Bhaban. You have just entered into a lift which has took you to a mysterious floor, Floor no. 20. In fact, you have got stuck into the lift and there is no way out of it except unlocking a Mysterious Lock. In order to unlock it, you have to solve a Puzzle.

The puzzle consists of a Binary Matrix of dimension N×MN \times M. A binary Matrix has 0 or 1 in each of it’s cells and it’s called Beautiful when each of its rows has an odd number of ones and each of its columns has an even number of ones.

Now, to unlock the mysterious lock, you have to transform the given matrix into a Beautiful one. In one move, you can flip any cell value of the matrix (flipping a value means, if there is a 00, after the move there will be a 11, and vice versa). But the time is short, you are suffocating inside the lift. So, you have to do it with a MinimumMinimum number of moves or report if it’s impossible to unlock the mysterious lock.

The rows are numbered from 11 to NN (top to bottom) and the columns are numbered from 11 to MM (left to right).

You have to print the minimum number of moves required to unlock the lock and the corresponding moves. If there are multiple solution, you can print any of them. If there is no solution, print “-1” (without quotes).

Input

The first line of input consists of two space separated integers NN and MM (1N,M10001 \leq N, M \leq 1000), representing the number of rows and the number of columns of the matrix respectively.

Next NN line contains MM characters each (each of which is either 0 or 1) representing the rows of the matrix.

Output

The first line of output will contain a single integer KK, the minimum number of moves required to unlock the lock or “-1” (without quotes) if it’s impossible to unlock.

If it’s possible to solve the puzzle, then next KK lines will print the moves. It will contain two space separated integers each, representing the co-ordinate of the cell which has been flipped on that move.


The output format will be of this form:
KK

X1X_{1} Y1Y_{1}

X2X_{2} Y2Y_{2}

XkX_{k} YkY_{k}

here XiX_{i} and YiY_{i} represents the row index of the cell (from top) and column index of the cell (from left) respectively.
(1XiN,1YiM1 \leq X_{i} \leq N, 1 \leq Y_{i} \leq M)

It is guaranteed that if there is a solution, then the number of moves of the solution will not exceed N x M.

Samples

InputOutput
4 3
101
011
100
110
3
1 1
2 1
4 1

After applying the 3 moves from output, the resultant matrix looks like this-

001
111
100
010

number of ones in rows are respectively 1, 3, 1, 1. All these values are odd.

number of ones in columns are respectively 2, 2, 2. All these values are even.

InputOutput
1 2
01
-1

There is no way to make this matrix beautiful.


Submit

Login to submit.

Statistics

77% Solution Ratio
Zobayer_AbedinEarliest, Mar '22
steinumFastest, 0.0s
steinumLightest, 5.5 kB
Zobayer_AbedinShortest, 1033B
Toph uses cookies. By continuing you agree to our Cookie Policy.