labirint

Let's take a rectangular shaped maze, containing n*m rooms arranged in the form of a matrix having n rows and m columns. We will consider the lines as being numbered from 1 to n and the columns as being numbered from 1 to m. The rooms of the maze have doors that open one-way, allowing movement to one of the 8 neighboring rooms. In order to code room exits, a positive integer from the [0, 255] interval will be stored in each matrix element coding the maze. Each bit 1 from the binary representation of a matrix element corresponds to a door in one of the possible movement direction, in the following order: N, NE, E, SE, S, SW, W, NW. More specifically, if the bit has value 1 there is a door in that bit's direction, and if the bit has value 0 that door doesn't exist. The bits are numbered starting with the least significant one.
There is a mouse in the maze, in the room on line L0 and column C0. The mouse would like to get out of the maze, but it can do it only once it has been through a specific number of rooms (nmin). As soon as it has gone through the nmin rooms the mouse can exit the maze. The mouse is smart and won't go through the same room twice. The mouse can only exit the maze if it is in a room that has a door in a direction that gets it outside the maze.

Task

Write a program that determines a route for the mouse, that has at least length nmin and that doesn't go through the same room twice. The route will begin in the mouse's initial room and will end in a room that has a door leading outside the maze.

Input Data

Output file labirint.in contains on line one two positive integers, separated by a space, n and m, with the meaning in the problem's statement. Each of the following n lines contain m positive integers separated by spaces, representing the maze's encoding. The next line of the input file contains two positive integers separated by a space, L0 and C0, representing the line and column corresponding to the room in which the mouse is in initially. The last line of the input file contains the minimum number of rooms the mouse has to go through before leaving the maze.

Output Data

Output file labirint.out will contain on the first line a positive integer Lg, representing the number of rooms the mouse can go through before leaving, without going through the same room twice and going through at least nmin rooms. The following Lg lines each contain two positive integers separated by a space, L C, representing the coordinates of the rooms (line, column) through which the mouse goes on its determined route.

Restrictions

• 0 < n, m <= 50
• The problem always has a solution for test data.

Examples

Time limit: 0.1 seconds/test

prof. Marinel Serban
"Grigore Moisil" Iaşi IT High School
Contact:marinel_serban@yahoo.com