Пирожок Дракона - это головоломка со скольжением на торе. Поверхность тора разбита на девять квадратов как показано на \textit{\textbf{Рисунке 1}}. Два квадрата с общей стороной обозначены одной буквой. На \textit{\textbf{Рисунке 2}} отображены пары квадратов, являющиеся соседними. Фишки пронумерованы числами от \textbf{1 }до \textbf{8 }и размещены на восьми из девяти квадратах, последний квадрат остается пустым. \includegraphics{https://static.e-olymp.com/content/78/7858fb96b184e7f067a77b55d1c87f721260ca7b.jpg} \textit{\textbf{Рисунок 1}}. \textbf{3}×\textbf{3} Тор Пирожка Дракона Фишка может перемещаться (скользить) в пустую ячейку из одной из соседних ячеек. Задача головоломки - путем перемещений фишек получить из начальной комбинации заданную. На \textit{\textbf{Рисунке 3}} приведен пример перемещений фишек из одного состояния в результате четырех возможных ходов. Стоимость перемещения фишки зависит от направления, но не от ее местоположения. Ваша задача - найти наименьшую стоимость перемещения фишек из начального состояния в конечное. \includegraphics{https://static.e-olymp.com/content/f9/f920169afb655d335b975fabb7680aaf2f43fb2f.jpg} \textit{\textbf{Рисунок 2}}. Соседы \includegraphics{https://static.e-olymp.com/content/98/9813bcb28e05bde85530eb9c3930c059cfa02907.jpg} \textit{\textbf{Рисунок 3}}. Примеры операций скольжения В отличии от задачи на плоскости, на торе любое конечное состояние фишек может быть получено из любого начального состояния. \InputFile Состоит из не более чем \textbf{30} тестов. Каждый тест состоит из семи строк. Первая строка содержит два натуральных числа \textbf{c_h} и \textbf{c_v} - стоимость передвижения фишки в горизонтальном и вертикальном направлении. Оба значения \textbf{c_h} и \textbf{c_v} меньше \textbf{100}. Следующие три строки задают начальное расположение, а последние три строки - финальное в следующем формате: \textbf{d_A d_B d_C} \textbf{d_D d_E d_F} \textbf{d_G d_H d_I} Каждая строка содержит три цифры, разделенных пробелом. Цифра \textbf{d_X} (\textbf{X }одна из букв от \textbf{A} до \textbf{I}) указывает на состояние квадрата \textbf{X} как показано на\textit{\textbf{ Рисунке 2}}. Цифры \textbf{1}, ..., \textbf{8} указывают на номер фишки в квадрате. Цифра \textbf{0 }означает, что квадрат пустой. Последняя строка содержит два нуля и не обрабатывается. \OutputFile Для каждого теста вывести в отдельной строке наименьшую стоимость, за которую можно получить конечное состояние. Общая стоимость равна сумме стоимостей ходов всех фишек из начального состояния в конечное.