print2156. Балкон замка

printБалкон замка

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Прекрасные король и королева Личного королевства, как и положено, живут в прекрасном замке. С верхнего этажа замка открывается замечательный вид на все Личное королевство, там и разместили свои апартаменты супруги. Заметим, что верхний этаж представляет из себя одну прямоугольную комнату шириной `w` и длиной `l` метров и таким образом состоит из `w\ times\ l` клеток.
Как и положено, мать королевы, то есть теща короля, является феей. А что же ей делать в небольшом, хоть и Личном, королевстве? Конечно же, проверять чувства супругов!
И вот однажды, когда король и королева находились на верхнем этаже замка порознь друг от друга, фея возвела на некоторых участках этажа преграды, а лестницы, ведущие с этажа, заблокировала. Попросту говоря, фея создала из этажа лабиринт, и теперь для того, чтобы продемонстрировать свою любовь, король и королева должны найти друг друга в нем. Если же этого не произойдет, то взамен приятных и спокойных вечеров супругов ждут многочасовые нравоучения.
Что же может спасти от этого ужаса? Во-первых, изобретение зодчих Личного королевства – балкон. Технические достижения пока позволяют возвести один балкон размерами `1\ times\ 3` метра. Таким образом, король может отдать поручение к трем подряд идущим (как сверху вниз, так и слева направо) внешним клеткам этажа пристроить балкон и сломать стены между балконом и теми клетками этажа, которые не были перегорожены феей. Возможно, именно проход, образованный балконом замка, поможет встретиться супругам.
Во-вторых, это вы! Как программисты Личного королевства, подскажите королю, каков может быть результат его стараний.
В первой строке входного файла содержатся два числа `w` и `l` (`3\ ≤\ w,\ l\ ≤\ 1000`) – ширина и длина этажа замка. Каждая из следующих `w` строк содержит по `l` символов в каждой. Символ "." значит, что по данной клетке этажа можно свободно перемещаться; символ "*" значит, что данную клетку фея заблокировала; символы "k" и "q" обозначают, соответственно, начальные положения короля и королевы.
Выведите в выходной файл "That is not a problem", если король может встретиться с супругой и без постройки балкона; "We can build a good balcony to be happy", если только строительство балкона поможет встретиться королю и королеве, и "Good work, dear fairy", если даже строительство балкона не поможет встретиться королю и королеве.

Пример ввода 1

4 4
k...
****
.***
...q

Пример вывода 1

We can build a good balcony to be happy

Пример ввода 2

4 4
k...
****
****
...q

Пример вывода 2

Good work, dear fairy

Пример ввода 3

4 4
k...
.***
.***
...q

Пример вывода 3

That is not a problem
Источник: neerc.ifmo.ru/school
loading