В верхнем левом углу прямоугольного поля размерами N×M размещается игральный кубик, разворот которого изображен на рисунке. Кубик ориентирован так, что передней грани соответствует единица, а слева находится грань, которой соответствует двойка. Клетки поля квадратные, их размеры совпадают с размерами грани кубика.
Кубик может двигаться по полю, переворачиваясь через одно из ребер, и попадать при этом в соседнюю снизу, сверху, справа или слева клетку поля. Например, если из начального состояния кубик двигается направо, то передней станет грань с двойкой, а если вниз — то с тройкой. Кубик не может выходить за пределы поля.
Напишите программу CASINO, которая по информации о поле находит один из возможных путей кубика из верхнего левого угла в нижний правый угол поля. При этом необходимо найти такой путь, чтобы передняя грань кубика в целевой клетке имела максимальное возможное значение. Кубик может посещать каждую клетку поля несколько раз.
Первая строка входного файла содержит два натуральных числа N и M (2 ≤ N, M ≤ 50), которые определяют высоту и ширину поля соответственно. Далее задается поле, которое представлено N строками, каждая из которых состоит из M чисел, каждое из которых равно 0 либо 1. В случае, когда клетке поля соответствует число 1, кубику запрещено посещать данную клетку. В противном случае эта клетка может встречаться в пути кубика. Начальной клетке всегда соответствует число 0.
Первая строка выходного файла должна содержать натуральное число W — длину найденного пути. Далее в файле должны находиться W строк, каждая из которых задает координату клетки поля на текущем шаге. Координата представляет собой пару натуральных чисел: номер строки и номер столбца клетки поля.
В случае, когда искомого пути не существует, выходной файл должен содержать строку с числом -1.