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