Casino
In the top-left corner of a rectangular field with dimensions N×M, a die is placed. The unfolded view of the die is shown in the figure. Initially, the die is positioned so that the front face displays a one, and the left face shows a two. The field is composed of square cells, each matching the size of the die's face.
The die can move across the field by rolling over one of its edges, landing in an adjacent cell either below, above, to the right, or to the left. For instance, if the die rolls to the right from its starting position, the front face will show a two, and if it rolls downward, it will show a three. The die must remain within the boundaries of the field.
Your task is to write a program named CASINO that, given the field's layout, determines one possible path for the die from the top-left corner to the bottom-right corner. The goal is to ensure that the front face of the die displays the highest possible value when it reaches the final cell. The die is allowed to visit each cell multiple times.
Input
The first line of the input contains two natural numbers N and M (2 ≤ N, M ≤ 50), representing the height and width of the field, respectively. The field is described by N rows, each containing M numbers, either 0 or 1. A cell marked with 1 is off-limits for the die, while a cell marked with 0 can be included in the die's path. The starting cell is always marked with 0.
Output
The first line of the output should contain a natural number W — the length of the discovered path. Following this, the output should include W lines, each indicating the coordinates of a field cell at each step. The coordinates are given as a pair of natural numbers: the row number and the column number of the cell.
If no valid path exists, the output should consist of a single line with the number -1.