Спелеология — увлекательное занятие. Но оно сопряжено с определенным риском. По статистике МЧС, наиболее часто несчастные случаи случаются со спелеологами весной, из-за неожиданных затоплений пещеры. За последние несколько лет было проведено столько спасательных операций! А на каждую требуется немалое количество ресурсов — людских, финансовых… В целях экономии средств, на последнем экстренном заседании министерства было принято следующее решение:

-----------------------
Приказ № 321/1.
В целях экономии средств на весенних спасательных операциях, приказываю:

1. Создать базу данных всех пещер и всех спелеологов РФ.
2. Вывести на геостационарную орбиту 12 спутников С-349857 для реализации возможности точного определения расположения спелеолога в пещере.
3. Привлечь программистов к разработке системы управления спутниками.
4. Создать прибор, взаимодействующий со спутниками, предназначенный для автоматической выдачи спелеологу инструкций по спасению. Описание требований к программному комплексу — приложения А и Б к данному приказу.
5. Обязать спелеологов брать с собой спецоборудование МЧС для экстренной связи с центром спасательных операций. В том числе прибор, выдающий инструкции по спасению.

Министр. (министр@мчс.ру)

Приложение А. Требования к прибору.
Прибор состоит из двух подсистем.

1. Подсистема детектирования возможности автоматического спасения (ПДВАС).
   
   • по известной конфигурации пещеры необходимо определить, какая часть ее заполнена водой.
   • по известному положению спелеолога и данным о том, сколько он может держаться под водой без воздуха, определить, возможно ли его автоматическое спасение.
2. Подсистема выдачи инструкций по автоматическому спасению (ПВИПАС — спелеологический компас):
   • по известной точке, где находится спелеолог, определить, куда двигаться дальше, чтобы гарантированно выбраться на поверхность.

Приложение Б. Принципы заполнения пещер водой.
Данный документ является результатом исследований ИПИ (Институт Пещерных Исследований при МЧС России — ипи@мчс.ру). Пещера заполняется водой по следующему принципу:

1. Пещера рассматривается, как набор квадратных ячеек.
2. Ячейка заполняется водой, если существует путь из нее на поверхность.
3. Путь — это цепочка ячеек, имеющих общую сторону.

При этом рассматриваются лишь пути идущие из ячейки на поверхность, не имеющие сегментов, спускающихся вниз.
-----------------------

К сожалению, как обычно, вместо занятий своей основной работой, все сотрудники ВЦ МЧС (вц@мчс.ру) заняты подготовкой Чемпионата Урала. Так что реализовывать логику работы ПДВАС предстоит именно вам.

В первой строке находятся 5 чисел: W, H, X, Y, D — соответственно, ширина и глубина пещеры (в ячейках), координаты положения спелеолога, количество ячеек, которые может проплыть спелеолог. Далее идет H строчек, описывающих конфигурацию пещеры. Каждая строчка содержит ровно W символов: символ "#" — обозначает стену, т.е. ячейку, недоступную ни для спелеолога, ни для воды; символ "." (точка) обозначает воздух, т.е. ячейку, доступную для спелеолога и, возможно, для воды. Система должна быть способна работать в следующем диапазоне параметров: 1 ≤ W, H ≤ 500; 1 ≤ X ≤ W; 1 ≤ Y ≤ H. 1 ≤ D ≤ 1000. Ячейки нумеруются слева направо, снизу вверх. Гарантируется, что, пока пещера не затоплена, спелеолог может самостоятельно выбраться на поверхность.

Выведите «Can be rescued by himself», если спелеолог может выбраться из пещеры самостоятельно. В противном случае выведите «Rescue operation required».