용의 크룰러

용의 크룰러는 토러스(도넛 모양의 곡면) 위에서 조각을 미끄러뜨리는 슬라이딩 퍼즐이다. 토러스의 표면은 그림 1의 전개도처럼 정사각형 아홉 칸으로 나뉜다. 전개도에서 같은 문자가 붙은 두 변은 실제로 맞붙어 있으므로 그 변을 사이에 둔 두 칸은 서로 인접하고 변을 공유한다. 어느 칸이 어느 칸과 어떤 방향으로 인접한지는 그림 2에 나와 있다. 1부터 8까지 번호가 붙은 조각 여덟 개를 아홉 칸 중 여덟 칸에 놓고 남은 한 칸은 비워 둔다.

그림 1. $3 \times 3$ 용의 크룰러 토러스

빈 칸과 인접한 칸에 놓인 조각은 빈 칸으로 미끄러뜨릴 수 있다. 퍼즐의 목표는 조각을 여러 번 미끄러뜨려서 주어진 시작 배치를 주어진 목표 배치로 바꾸는 것이다. 그림 3은 가운데 배치에서 가능한 네 가지 미끄러뜨리기로 곧바로 도달하는 배치를 보여 준다. 조각 하나를 한 칸 미끄러뜨리는 비용은 방향에만 좌우되고 칸의 위치나 조각 번호와는 무관하다.

주어진 시작 배치를 주어진 목표 배치로 바꾸는 데 드는 최소 비용을 구하라.

그림 2. 인접 관계

그림 3. 미끄러뜨리기의 예

평면 정사각형 위의 일부 슬라이딩 퍼즐과 달리 이 토러스에서는 어떤 시작 배치에서도 어떤 목표 배치에 도달할 수 있다고 알려져 있다.

입력은 데이터 집합 최대 30개로 이루어진다.

각 데이터 집합은 일곱 줄이다. 첫 줄에는 양의 정수 $c_h$와 $c_v$가 주어진다. $c_h$는 조각을 좌우로 한 칸 옮기는 비용이고 $c_v$는 위아래로 한 칸 옮기는 비용이다. 둘 다 100보다 작다. 이어지는 세 줄은 시작 배치를 나타내고 그다음 세 줄은 목표 배치를 나타내며 형식은 다음과 같다.

dA dB dC
dD dE dF
dG dH dI

각 줄은 공백으로 구분한 숫자 세 개로 이루어진다. 숫자 $d_X$는 그림 2의 칸 X의 상태를 나타내고 X는 A부터 I까지 중 하나다. 숫자 1부터 8까지는 그 번호의 조각이 그 칸에 놓여 있다는 뜻이고 숫자 0은 그 칸이 비어 있다는 뜻이다.

입력의 끝은 공백으로 구분한 0 두 개로 나타낸다.

각 데이터 집합마다 목표 배치를 만드는 최소 총비용을 한 줄에 출력한다. 총비용은 시작 배치에서 목표 배치에 이르기까지 조각을 미끄러뜨린 비용의 합이다. 그 밖의 문자는 출력하지 않는다.