Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3081
The Grid

Time Limit: 1 Second      Memory Limit: 32768 KB

Some days ago, a game called "The grid" was introduced to watashi. It is a simple game, but not an easy one. The game is played on a three-dimensional grid, which contains P * Q * R lattices. And there are N numbers (from 1 to N) in these lattices, except an empty one, each lattice contains a distinct number, so here we have N = P * Q * R - 1. In each step, the player can move a number in a lattice, which is adjacent to the empty one, to the empty lattice. So after one step, the number player moved will change its position, and the old position of it will be empty. Now the task is: you've given a start state of the three-dimensional grid and an end state of the grid, start from the start state, find a way to the end state, using moving method described above.

But you know, watashi will never be satisfied at his achievement, so he wants to know how many steps can he finish the game at least. To simplify the problem, he likes the end state to be the same simple state, which described in the following section.


Input consists of several testcases(not exceed 50), each testcase starts with a line contains three integers: P, Q and R. Then followed by P blocks, each block contains Q lines, and each line contains R integers. These P * Q * R integers will be distinct, and the empty lattice will be marked by integer P * Q * R. These P blocks described the start state. The end state of each testcase will not be described in input, because they will be the same. So if it is described in method just like start state, integers will be placed from 1 to P * Q * R in ascending order. For example, if P = 3, Q = R = 2, the end state will be like this:

1 2
3 4
5 6
7 8
9 10
11 12

We guarantee that 1 <= P <=4, 1 <= Q <= 4, 1 <= R <= 4.


For each testcase, you should output the minimum number of steps to get to the end state from the start state in one line. If there isn't any way to get to the end state from the start state, output -1 please.

Sample Input

2 2 2
1 8
3 2
5 6
7 4

Sample Output


Author: FAN, Yuzhe
Source: ZOJ Monthly, December 2008
Submit    Status