Dragon's Cruller

Problem

Dragon's Cruller is a sliding puzzle on a torus. The torus surface is partitioned into nine squares, laid out as the development in Figure 1. Two sides of the development labeled with the same letter are glued together, so the two squares on those sides are adjacent and actually share the side. Figure 2 lists which square is adjacent to which, and in which direction. Pieces numbered 1 through 8 sit on eight of the nine squares, and the remaining square is empty.

Figure 1. A $3 \times 3$ Dragon's Cruller torus

A piece on a square adjacent to the empty square can be slid into the empty square. The goal of the puzzle is to reposition the pieces from the given starting arrangement into the given goal arrangement by sliding pieces a number of times. Figure 3 shows the arrangements reached directly from the arrangement in the center by the four possible slides. The cost of sliding a piece one square depends only on the direction, not on the square and not on the piece.

Find the minimum cost of repositioning the pieces from the given starting arrangement into the given goal arrangement.

Square	Horizontally adjacent squares	Vertically adjacent squares
A	B, I	G, D
B	C, A	H, E
C	D, B	I, F
D	E, C	A, G
E	F, D	B, H
F	G, E	C, I
G	H, F	D, A
H	I, G	E, B
I	A, H	F, C

Figure 2. Adjacency

Figure 3. Examples of sliding steps

Unlike some sliding puzzles on a flat square, it is known that every goal arrangement on this torus is reachable from every starting arrangement.

Input

The input is a sequence of at most 30 datasets.

A dataset consists of seven lines. The first line contains two positive integers $c_h$ and $c_v$ . $c_h$ is the cost of moving a piece one square horizontally and $c_v$ is the cost of moving it one square vertically. Both are less than 100. The next three lines specify the starting arrangement and the last three the goal arrangement, each in the following format.

dA dB dC
dD dE dF
dG dH dI

Each line consists of three digits separated by a space. The digit $d_X$ , where X is one of A through I, gives the state of square X in Figure 2. A digit from 1 to 8 means that the piece with that number is on the square. The digit 0 means that the square is empty.

The end of the input is indicated by two zeros separated by a space.

Output

For each dataset, print the minimum total cost of achieving the goal arrangement on one line. The total cost is the sum of the costs of the moves from the starting arrangement to the goal arrangement. Print no other characters.