Dragon’s Cruller 是一种在环面（torus）上进行的滑动拼图游戏。环面表面被划分为九个方格，如图 E.1 所示。在此展开图中，标有相同字母的边实际上是相邻的，并共享该边。图 E.2 展示了各方格之间的相邻关系及其方式。编号为 1 到 8 的棋子被放置在九个方格中的八个上，留下一个空格。
图 E.1. 3 × 3 Dragon’s Cruller 环面
棋子可以从相邻的方格滑动到空格中。拼图的目标是通过多次滑动棋子，将棋子从给定的初始排列移动到给定的目标排列。图 E.3 展示了从中心所示的排列经过四种可能的滑动后直接到达的排列。滑动棋子的代价取决于方向，但与位置或棋子本身无关。
你的任务是求出将棋子从给定的初始排列移动到给定的目标排列所需的最小代价。
图 E.2. 相邻关系
| 方格 | 水平相邻方格 | 垂直相邻方格 |
|---|---|---|
| $A$ | $B \quad I$ | $G \quad D$ |
| $B$ | $C \quad A$ | $H \quad E$ |
| $C$ | $D \quad B$ | $I \quad F$ |
| $D$ | $E \quad C$ | $A \quad G$ |
| $E$ | $F \quad D$ | $B \quad H$ |
| $F$ | $G \quad E$ | $C \quad I$ |
| $G$ | $H \quad F$ | $D \quad A$ |
| $H$ | $I \quad G$ | $E \quad B$ |
| $I$ | $A \quad H$ | $F \quad C$ |
图 E.3. 滑动步骤示例
与某些在平面正方形上的滑动拼图不同，已知在此环面上，任何目标排列都可以从任何初始排列到达。
输入格式
输入包含最多 30 组数据集。
每个数据集包含七行。第一行包含两个正整数 $c_h$ 和 $c_v$，分别表示水平移动和垂直移动棋子的代价。你可以假设 $c_h$ 和 $c_v$ 均小于 100。接下来的三行指定初始排列，最后三行指定目标排列，格式如下：
$d_A \ d_B \ d_C$ $d_D \ d_E \ d_F$ $d_G \ d_H \ d_I$
每行包含三个由空格分隔的数字。数字 $d_X$（$X$ 为 $A$ 到 $I$ 之一）表示如图 E.2 所示的方格 $X$ 的状态。数字 $1, \dots, 8$ 表示该编号的棋子位于该方格上。数字 $0$ 表示该方格为空。
输入结束由两个由空格分隔的零表示。
输出格式
对于每个数据集，输出达到目标所需的最小总代价，占一行。总代价是从初始排列到目标排列的移动代价之和。输出中不应包含其他字符。
样例
输入 1
4 9 6 3 0 8 1 2 4 5 7 6 3 0 8 1 2 4 5 7 31 31 4 3 6 0 1 5 8 2 7 0 3 6 4 1 5 8 2 7 92 4 1 5 3 4 0 7 8 2 6 1 5 0 4 7 3 8 2 6 12 28 3 4 5 0 2 6 7 1 8 5 7 1 8 6 2 0 3 4 0 0
输出 1
0 31 96 312