Cave
Dwarf Thorin has discovered a map of an abandoned cave once inhabited by the mountain king Norus. This map reveals the location of a vast treasure. To safeguard his riches from treasure hunters, the mountain king placed L stone blocks within the cave. These blocks are capable of moving and can crush anyone in their path, but they will stop once the treasure is found.
The map is represented as a rectangular integer matrix of dimensions M×N. The elements of this matrix can be: -2 (indicating the treasure), -1 (a wall), 0 (an empty space), or a positive integer K (indicating a part of the K-th block). Each K-th block comprises all elements marked with the number K. A block may not be contiguous, but all its elements move in unison. Zeros located in the outermost rows or columns of the matrix denote entrances to the cave. The initial movement direction for each block is provided separately (1 for up, 2 for right, 3 for down, 4 for left).
The dwarf starts at an entrance cell. He moves according to these rules: each second, the dwarf first moves to an adjacent empty cell (up, down, left, or right) or remains stationary. During the same second, each block moves one cell in its current direction: first the first block, then the second, and so on. If a wall, the edge of the cave, the treasure, or another block is in front of any block element in its direction of movement, the block does not move that turn, and its movement direction is reversed. If a block lands on the dwarf's cell during its movement, the dwarf perishes.
Write a program, CAVE, to determine a safe path to the treasure in the shortest possible time, assuming such a path exists.
Input
The input file begins with three numbers on the first line: M, N, and L — the number of blocks (3 ≤ M ≤ 75, 3 ≤ N ≤ 75, 0 ≤ L ≤ 1000). The next M lines contain N integers each, representing the cave map. The following L lines specify the initial movement directions for the blocks, listed in increasing order of their numbers.
Output
The output file should first contain the number K — the time in seconds to reach the treasure. In the subsequent K+1 lines, list the coordinates of the dwarf's position at each second (starting with the entrance coordinates). The coordinates should be presented in the format "row column". If multiple paths exist, providing any one of them is sufficient.