Всем известно, что нелегко живётся змейкам в лабиринтах. Даже если змейка одна в лабиринте, она может погибнуть, врезавшись в стену или в свой хвост. Некто Вася, претендент на победу в конкурсе змеек, решил научить свою змейку выбираться из опасных частей лабиринта. Опасность таких <<подлабиринтов>> в том, что шансы змейки выбраться оттуда живой малы, и, конечно, чем длиннее змейка, тем ниже шансы. Вася проводит обучение змейки так: в юном возрасте, когда длина змейки достигает \textbf{2}, Вася запускает змейку в тренировочный опасный лабиринт; цель змейки--- выбраться оттуда как можно быстрее, если она выживает, то по достижении длины \textbf{3} обучение повторяется в том же лабиринте, и так пока змейка не станет совершенно длинной (длины \textbf{18}) либо не погибнет. Лабиринт можно представить себе как прямоугольник ширины \textbf{W} и длины \textbf{H}, каждая клетка которого --- либо препятствие '\textbf{X}', либо свободное место '\textbf{.}'. Лабиринт окружён непроходимыми камнями '\textbf{*}', за исключением одной клетки '\textbf{#}', смежной входу в лабиринт, который расположен на границе лабиринта. Вот, например, простой лабиринт длины \textbf{4} и ширины \textbf{3}: \includegraphics{https://static.e-olymp.com/content/c0/c0e7e481142bab02ea22da6e1d5b8887480141e8.jpg} Змейка длины \textbf{L} представляет собой последовательность из \textbf{L} клеток. Каждая клетка последовательности смежна с соседними клетками по стороне. Все клетки в последовательности различны. Змейка может ползти относительно текущего направления движения в трёх направлениях: прямо, налево или направо. Змейка ползёт одновременно всем телом, и каждая клетка, кроме первой, занимает место предыдущей. Вот примеры допустимых движений змейки: \textbf{321. -> .321} \textbf{321 -> .32} \textbf{... ..1} \textbf{12 -> 23} \textbf{.3 1.} \textbf{12 -> 23} \textbf{43 14} Змейка за каждую единицу времени проползает ровно одну клетку, если же ей некуда ползти, то она погибает. \InputFile В первой строке находятся размеры лабиринта \textbf{H} и \textbf{W} (\textbf{1} ≤ \textbf{H} ≤ \textbf{300}, \textbf{1} ≤ \textbf{W} ≤ \textbf{30}). Во второй строке находятся координаты входа \textbf{h_0} и \textbf{w_0}. Причем либо \textbf{h_0 = 1}, либо \textbf{h_0 = H}, либо \textbf{w_0 = 1}, либо \textbf{w_0 = W}. Далее следуют \textbf{H} строк по \textbf{W}символов --- построчное описание лабиринта, где '\textbf{X}' обозначает препятствие, а '\textbf{.}' свободную клетку. Отсчёт времени начинается с \textbf{0}; начальное положение змейки: голова в точке (\textbf{h_0}, \textbf{w_0}), остальная часть тела снаружи. Отсчёт времени заканчивается, когда голова змейки вновь окажется в клетке (\textbf{h_0}, \textbf{w_0}). И ещё, лабиринт хоть и тренировочный, но ни одна змейка длины \textbf{18} не может выбраться оттуда живой. \OutputFile Выход должен содержать \textbf{16} строчек, где \textbf{i}-я строчка представляет собой лучшее время, за которое змейка длины\textbf{i+1} может выбраться из лабиринта, либо \textbf{−1}, если она неминуемо погибает.