Подорожуючий Куб
На маленькій планеті під назвою Бандай десантна група зорельота Тадамігава виявила кольорові кубики, що переміщуються по плоских ділянках поверхні планети, які десантна група назвала ліжками. Кубик з'являється в певному положенні на ліжку, подорожує по ньому деякий час, а потім зникає. Після тривалого спостереження науковий офіцер лейтенант Аліса Огава з Тадамігава виявила правило, за яким кубик подорожує по ліжку.
Ліжко — це прямокутна ділянка, вкрита квадратами однакового розміру.
Один з квадратів пофарбований у червоний колір,
один пофарбований у зелений,
один пофарбований у синій,
один пофарбований у блакитний,
один пофарбований у пурпурний,
один пофарбований у жовтий,
один або більше пофарбовані у білий, і
всі інші, якщо такі є, пофарбовані у чорний.
Спочатку кубик з'являється на одному з білих квадратів. Грани кубика пофарбовані наступним чином.
Кубик може перекочуватися через сторону поточного квадрата за один крок і таким чином перекочується на сусідній квадрат. Коли кубик перекочується на хроматично пофарбований (червоний, зелений, синій, блакитний, пурпурний або жовтий) квадрат, верхня грань кубика після перекочування повинна бути пофарбована так само. Коли кубик перекочується на білий квадрат, таке обмеження відсутнє. Кубик ніколи не повинен перекочуватися на чорний квадрат.
Протягом подорожі кубик може відвідати кожен з хроматично пофарбованих квадратів лише один раз, а будь-який з білих квадратів — скільки завгодно разів. Як вже згадувалося, кубик ніколи не може відвідати жоден з чорних квадратів. Під час відвідування останнього хроматично пофарбованого квадрата кубик зникає. Якимось чином порядок відвідувань хроматично пофарбованих квадратів відомий нам до початку подорожі.
Ваше завдання — знайти найменшу кількість кроків, щоб кубик відвідав усі хроматично пофарбовані квадрати у заданому порядку.
Вхідні дані
Вхідні дані — це послідовність наборів даних. Набір даних форматований наступним чином:
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", якщо рішення немає. У будь-якому випадку виведіть це в одному рядку для кожного набору вхідних даних.