Как известно, наиболее сложно при управлении автомобилем (на дорогах с правосторонним движением) поворачивать налево, поскольку при этом нужно пропускать автомобили, двигающиеся навстречу. Поэтому в некотором городе запретили все повороты налево, то есть на перекрёстках можно либо продолжить движение в том же направлении, либо повернуть направо. Разворачиваться и поворачивать налево на перекрёстках запрещено.
План города представляет собой прямоугольную сетку, в узлах сетки находятся перекрёстки, соединённые дорогами. Расстояние между перекрёстками равно 1. Но некоторые проезды между перекрёстками закрыты, передвигаться можно только по белым улицам (в том числе и по внешней белой границе), проезжать по серым улицам и перекрёсткам нельзя.
Ваш автомобиль находится на отмеченном изображением автомобиля перекрёстке и движется в направлении стрелки. То есть следующий перекрёсток, на который может приехать автомобиль, находится в направлении стрелки.
Вам необходимо приехать на перекрёсток, обозначенный звёздочкой. Вы можете приехать на этот перекрёсток с любой из трёх возможных сторон.
Постройте не содержащий левых поворотов маршрут автомобиля кратчайшей длины.
Ответ необходимо записать в виде последовательности целых чисел, каждое число может принимать значение от 1 до 9. Число равно количеству кварталов (промежутков между перекрёстками), которое автомобиль проезжает в прямом направлении, затем автомобиль поворачивает направо.
Например, последовательность “4 1” означает, что автомобиль проезжает 4 квартала, поворачивает направо, затем проезжает 1 квартал. В этом случае автомобиль завершит движение в правом нижнем углу карты, если он стартует в направлении стрелки.