DFLOOR - Dance Floor

You recently watched a video clip in which a singer danced on a grid of colourful tiles enlightened from below. Each step on a tile flipped the tile's state, i.e. light on or off. In addition to that, all the neighbouring tiles flipped their states, too.

In this task, you are supposed to come up with a short program that decides if it is possible for the singer to switch on the lights of all the tiles, provided that he dances on the appropriate tiles.

The dance floor has rectangular shape. At the beginning, some of the tiles are already alight. Your program may temporarily switch off some tiles, if it deems that necessary to reach its goal. Stepping on a tile toggles its own state as well as the states of the four neighbouring tiles directly above, below, to the left and to the right. Of course, in the case of a peripheral tile, there will be only three or two neighbouring tiles.

Here comes an example:

If the dancer steps on the tile indicated by the brown shoe, all the tiles within the white area change their states. The resulting dance floor is depicted on the right.

You may assume that the singer is fit enough to jump from any tile to any other tile, even if the destination tile lies on the opposite side of the dance floor.

Input

There are several test cases. The first line of each case contains two integer numbers x and y, indicating the width and the height of the dance floor grid. The numbers are separated by a single space and satisfy 3 ≤ x,y ≤ 15.

The following y lines containing xcharacters each describe the initial on/off states of the tiles. A zero means "the tile is switched off", a one digit means "the tile is alight".

Input ends with 0 0.

Output

For each test case your program should output the number of steps needed to switch all the lights on, followed by exactly that many lines with two space-separated numbers i and j. Each individual line commands the singer to step on the i-th tile of the j-th row. Starting with the situation of the input file and executing all the commands in the output file, all the tiles must be switched on.

If more than one solution exist, your program should output an arbitrary one of them. If, on the other hand, no solution exists, your program should write the number "-1".

Example

Sample input

4 3 0111 1010 1000 0 0

Sample output

3 1 2 1 3 4 3

Added by:Michał Czuczman
Date:2004-07-01
Time limit:2.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Swiss Olympiad in Informatics 2004

hide comments
2012-05-20 23:15:09 15972125841321
do we have to output the minimum number of steps with its solution or all the possible solutions with their steps??
2012-04-30 19:25:44 Noszály Csaba
BTTNS is a similar task.
2011-12-30 07:31:55 Prakash Y
How can i submit the code and verify whether my program is correct or not?
2011-11-08 19:54:52 :-P
something about that http://aix1.uottawa.ca/~jkhoury/game.html

Last edit: 2011-11-08 19:55:35
2011-03-27 20:41:31 :D
Also see CERC07B
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.