Всем известно, что нелегко живётся змейкам в лабиринтах. Даже если змейка одна в лабиринте, она может погибнуть, врезавшись в стену или в свой хвост. Некто Вася, претендент на победу в конкурсе змеек, решил научить свою змейку выбираться из опасных частей лабиринта. Опасность таких «подлабиринтов» в том, что шансы змейки выбраться оттуда живой малы, и, конечно, чем длиннее змейка, тем ниже шансы. Вася проводит обучение змейки так: в юном возрасте, когда длина змейки достигает 2, Вася запускает змейку в тренировочный опасный лабиринт; цель змейки— выбраться оттуда как можно быстрее, если она выживает, то по достижении длины 3 обучение повторяется в том же лабиринте, и так пока змейка не станет совершенно длинной (длины 18) либо не погибнет.

Лабиринт можно представить себе как прямоугольник ширины W и длины H, каждая клетка которого — либо препятствие 'X', либо свободное место '.'. Лабиринт окружён непроходимыми камнями '*', за исключением одной клетки '#', смежной входу в лабиринт, который расположен на границе лабиринта. Вот, например, простой лабиринт длины 4 и ширины 3:

***#**
*.X.X*
*.X..*
*....*
******

Змейка длины L представляет собой последовательность из L клеток. Каждая клетка последовательности смежна с соседними клетками по стороне. Все клетки в последовательности различны. Змейка может ползти относительно текущего направления движения в трёх направлениях: прямо, налево или направо. Змейка ползёт одновременно всем телом, и каждая клетка, кроме первой, занимает место предыдущей. Вот примеры допустимых движений змейки:

• 321. -> .321

• 321 -> .32
  ...    ..1
  

• 12 -> 23
  .3    1.
  

• 12 -> 23
  43    14
  

Змейка за каждую единицу времени проползает ровно одну клетку, если же ей некуда ползти, то она погибает.

В первой строке находятся размеры лабиринта H и W (1 ≤ H ≤ 300, 1 ≤ W ≤ 30). Во второй строке находятся координаты входа h₀ и w₀. Причем либо h₀ = 1, либо h₀ = H, либо w₀ = 1, либо w₀ = W. Далее следуют H строк по W символов — построчное описание лабиринта, где 'X' обозначает препятствие, а '.' свободную клетку. Отсчёт времени начинается с 0; начальное положение змейки: голова в точке (h₀,w₀), остальная часть тела снаружи. Отсчёт времени заканчивается, когда голова змейки вновь окажется в клетке (h₀,w₀). И ещё, лабиринт хоть и тренировочный, но ни одна змейка длины 18 не может выбраться оттуда живой.

Выход должен содержать 16 строчек, где i-я строчка представляет собой лучшее время, за которое змейка длины i+1 может выбраться из лабиринта, либо −1, если она неминуемо погибает.