Сон Бессі
Після того, як Бессі наїлася фруктів на кухні Фермера Джона, їй наснилися дивні сни. Вона опинилася в лабіринті, що має форму решітки розміром n на m клітинок. Бессі починає свій шлях у лівій верхній клітинці і прагне дістатися до правої нижньої. З кожної клітинки вона може рухатися в одному з чотирьох напрямків: вгору, вниз, вправо або вліво.
Але є одна умова! Кожна клітинка має свій колір, і кожен колір має свої особливості:
Червона клітинка (red) є непрохідною.
Рожева клітинка (pink) є прохідною.
Помаранчева клітинка (orange) також є прохідною, але після відвідування Бессі починає пахнути апельсином.
Синя клітинка (blue) містить піраній, і Бессі може пройти через неї лише якщо пахне апельсином.
Пурпурова клітинка (purple) змушує Бессі ковзати в напрямку руху (якщо наступна клітинка прохідна). Якщо наступна клітинка також пурпурова, Бессі продовжує ковзати, доки не досягне непурпурової або непрохідної клітинки. Ковзання через одну клітинку рахується як один крок. Пурпурові клітинки також усувають запах апельсина.
(Приклад нижче детальніше пояснює властивості пурпурових клітинок)
Допоможіть Бессі дістатися з лівого верхнього кута до правого нижнього за мінімально можливу кількість кроків.
Вхідні дані
Перший рядок містить два цілі числа n і m (1 ≤ n, m ≤ 1000), що визначають кількість рядків і стовпців лабіринту.
Кожен з наступних n рядків містить m цілих чисел, що описують лабіринт:
Число '0' позначає червону клітинку.
Число '1' позначає рожеву клітинку.
Число '2' позначає помаранчеву клітинку.
Число '3' позначає синю клітинку.
Число '4' позначає пурпурову клітинку.
Ліва верхня і права нижня клітинки завжди будуть '1'.
Вихідні дані
Одне ціле число, що представляє мінімальну кількість кроків, які має зробити Бессі, щоб пройти лабіринт, або -1, якщо це неможливо.
Приклад
У цьому прикладі Бессі спочатку йде один квадрат вниз, потім два квадрати вправо (і ковзає ще один квадрат вправо). Далі вона йде один квадрат вгору, один квадрат вліво, один квадрат вниз (ковзає два квадрати вниз) і завершує рух, переміщуючись на один квадрат вправо. Загалом вона зробить 10 кроків (DRRRULDDDR).