Змійка
Відомо, що змійкам нелегко виживати в лабіринтах. Навіть якщо змійка одна в лабіринті, вона може загинути, врізавшись у стіну або у свій хвіст. Вася, який прагне перемогти в конкурсі змійок, вирішив навчити свою змійку уникати небезпечних ділянок лабіринту. Небезпека таких "підлабіринтів" полягає в тому, що шанси змійки вибратися звідти живою невеликі, і чим довша змійка, тим менші ці шанси. Вася тренує змійку так: коли її довжина досягає 2, він запускає її в тренувальний небезпечний лабіринт. Мета змійки — вибратися звідти якомога швидше. Якщо вона виживає, то при досягненні довжини 3 навчання повторюється в тому ж лабіринті, і так далі, поки змійка не стане дуже довгою (довжини 18) або не загине.
Лабіринт можна уявити як прямокутник ширини W і висоти H, де кожна клітинка — або перешкода 'X', або вільне місце '.'. Лабіринт оточений непрохідними каменями '*', за винятком однієї клітинки '#', яка прилягає до входу в лабіринт, розташованого на межі лабіринту. Ось, наприклад, простий лабіринт висотою 4 і шириною 3:
Змійка довжини L складається з послідовності з L клітинок. Кожна клітинка послідовності суміжна з сусідніми клітинками по стороні. Усі клітинки в послідовності різні. Змійка може рухатися відносно поточного напрямку в трьох напрямках: прямо, наліво або направо. Змійка рухається всім тілом одночасно, і кожна клітинка, крім першої, займає місце попередньої. Ось приклади допустимих рухів змійки:
321. -> .321
321 -> .32
... ..1
12 -> 23
.3 1.
12 -> 23
43 14
Змійка за кожну одиницю часу проповзає рівно одну клітинку. Якщо їй нікуди повзти, вона гине.
Вхідні дані
У першому рядку подано розміри лабіринту H і W (1 ≤ H ≤ 300, 1 ≤ W ≤ 30). У другому рядку подано координати входу h_0 і w_0. Причому або h_0 = 1, або h_0 = H, або w_0 = 1, або w_0 = W. Далі йдуть H рядків по W символів — построчний опис лабіринту, де 'X' позначає перешкоду, а '.' — вільну клітинку. Відлік часу починається з 0; початкове положення змійки: голова в точці (h_0, w_0), решта частини тіла зовні. Відлік часу закінчується, коли голова змійки знову опиниться в клітинці (h_0, w_0). І ще, лабіринт хоч і тренувальний, але жодна змійка довжини 18 не може вибратися звідти живою.
Вихідні дані
Вихід повинен містити 16 рядків, де i-й рядок представляє найкращий час, за який змійка довжини i+1 може вибратися з лабіринту, або −1, якщо вона неминуче гине.