Путешествующий Куб
На небольшой планете под названием Бандай команда звездолета Тадамигава обнаружила разноцветные кубы, которые перемещаются по плоским участкам поверхности, названным "кроватями". Куб появляется в определенной точке на кровати, некоторое время движется по ней, а затем исчезает. После длительных наблюдений научный офицер лейтенант Алиса Огава из Тадамигава выявила правило, по которому куб перемещается по кровати.
Кровать представляет собой прямоугольную область, выложенную квадратами одинакового размера.
Один из квадратов окрашен в красный цвет,
один в зеленый,
один в синий,
один в циан,
один в пурпурный,
один в желтый,
один или более окрашены в белый, и
все остальные, если таковые имеются, окрашены в черный.
Изначально куб появляется на одном из белых квадратов. Грани куба окрашены следующим образом.
Куб может перекатываться через сторону текущего квадрата за один шаг, перемещаясь на соседний квадрат. Когда куб перекатывается на хроматически окрашенный (красный, зеленый, синий, циан, пурпурный или желтый) квадрат, верхняя грань куба после переката должна быть окрашена в тот же цвет. При перекате на белый квадрат такого ограничения нет. Куб никогда не должен перекатываться на черный квадрат.
На протяжении всего перемещения куб может посетить каждый из хроматически окрашенных квадратов только один раз, а любой из белых квадратов — сколько угодно раз. Как уже упоминалось, куб никогда не может посетить черные квадраты. При посещении последнего хроматически окрашенного квадрата куб исчезает. Порядок посещения хроматически окрашенных квадратов известен заранее.
Ваша задача — найти минимальное количество шагов, чтобы куб посетил все хроматически окрашенные квадраты в заданном порядке.
Входные данные
Входные данные состоят из нескольких наборов. Каждый набор данных форматируется следующим образом:
w d
c_11...c_w1
...
c_1d...c_wd
v_1v_2v_3v_4v_5v_6
Первая строка содержит два положительных целых числа w и d, разделенных пробелом. Следующие d строк содержат строки длиной w символов c_11...c_w1, ..., c_1d...c_wd без пробелов. Каждый символ c_ij — это одна из букв r, g, b, c, m, y, w и k, обозначающих красный, зеленый, синий, циан, пурпурный, желтый, белый и черный соответственно, или знак #. Каждая из r, g, b, c, m, y и # встречается ровно один раз в наборе данных. Последняя строка — это строка длиной шесть символов v_1v_2v_3v_4v_5v_6, которая является перестановкой "rgbcmy".
Целые числа w и d обозначают ширину (длину от восточного конца до западного) и глубину (длину от северного конца до южного) кровати. Единица измерения — длина стороны квадрата. Можно предположить, что ни w, ни d не превышают 30.
Каждый символ c_ij показывает цвет квадрата на кровати. Символы c_11, c_w1, c_1d и c_wd соответствуют северо-западному углу, северо-восточному углу, юго-западному углу и юго-восточному углу кровати соответственно. Если c_ij — это буква, она указывает цвет соответствующего квадрата. Если c_ij — это #, соответствующий квадрат окрашен в белый и является начальной позицией куба.
Строка v_1v_2v_3v_4v_5v_6 показывает порядок цветов квадратов для посещения. Куб должен посетить квадраты, окрашенные в v_1, v_2, v_3, v_4, v_5 и v_6 в этом порядке.
Конец ввода обозначается строкой, содержащей два нуля, разделенных пробелом.
Выходные данные
Для каждого набора данных на входе выведите минимальное количество шагов, если решение существует, или "unreachable", если решения нет. В любом случае выведите это в одной строке для каждого набора данных на входе.