Speleology is a very interesting occupation. But it is also quite risky. According to the statistics, accidents are most often in spring, and many of them are caused by unexpected cave floods. In the last few years, there were several rescue operations, and each of them required quite a lot of financial resources and manpower. For the sake of economy, the Ministry for Extreme Situations issued the following order.
Order № 321/1.
For the sake of economy of resources at spring rescue operations, it is ordered to:
- Create a database of all caves and all speleologists of the Russian Federation.
- Put into geostationary orbits 12 satellites S-349857 to make possible the exact determination of the location of speleologists in caves.
- Employ programmers to develop systems of satellite control.
- Create a device interacting with the satellites for automatically issuing rescue instructions to a speleologist. The device specification is given in Appendices A and B.
- Oblige speleologists to have special equipment for urgent communication with a rescue center, including the device described in Article 4.
Appendix A. The device specification.
The device has two modules.
- The module for detecting the possibility of automated rescue (MDPAR):
- determines which part of a cave is filled with water for the known configuration of the cave;
- determines whether automated rescue is possible if the location of a speleologist and the maximal duration of his underwater stay are known.
- The module for issuing instructions for automated rescue (MIIAR):
- given the location of a speleologist, determines the direction of movement guaranteeing reaching the surface.
Appendix B. The principles of filling caves with water.
This document is a result of investigations of the Institute for Cave Studies.
A cave is filled with water according to the following rules:
- The cave is regarded as a collection of cubicles.
- A cubicle is filled with water if there is a path from this cubicle to the surface.
- A path is a sequence of cubicles that have common side.
Here only the paths having no downward segments are considered.
You are to implement the MDPAR.
The first line contains 5 integers W, H, X, Y, D, which are respectively the width and depth of a cave (in cubicles), the X and Y coordinates of a speleologist, and the number of cubicles through which he can swim without air. The following H lines describe the configuration of the cave. Each of these lines contains W characters: "#" denotes a wall, i.e., a cubicle inaccessible both for the speleologist and for water, and a dot "." denotes air, i.e., a cubicle that is possibly accessible for the speleologist and can be filled with water. The module should be able to operate in the following ranges of the parameters: 1 ≤ W, H ≤ 500; 1 ≤ X ≤ W; 1 ≤ Y ≤ H. 1 ≤ D ≤ 1000. Cubicles are numbered from left to right, from bottom to top.
It is known that a speleologist can reach the surface while cave is not filled with water.
You should output "Can be rescued by himself" if the speleologist can reach the surface following the instructions issued by the MIIAR. Otherwise, you should output "Rescue operation required".
9 4 8 2 5
Rescue operation required
9 4 8 2 6
Can be rescued by himself
Problem Author: Idea - Alexander Klepinin, prepared by Alexander Klepinin, Ivan Dashkevich
Problem Source: VIII Collegiate Students Urals Programming Contest. Yekaterinburg, March 11-16, 2004