Traveling Cube

On a small planet called Bandai, a landing party from the starship Tadamigawa found colorful cubes rolling across flat areas of the surface, which they named beds. A cube appears at some position on a bed, travels for a while, and then disappears. Science officer Lt. Alyssa Ogawa worked out the rule by which a cube travels.

A bed is a rectangular area tiled with equal squares. Exactly one square is red, one green, one blue, one cyan, one magenta, and one yellow; one or more squares are white; and every remaining square is black.

A cube first appears on a white square. Its faces are colored: top red, bottom cyan, north green, south magenta, east blue, west yellow.

At each step the cube rolls over one of its four bottom edges onto the adjacent square. When the cube rolls onto a chromatic square (red, green, blue, cyan, magenta, or yellow), the top face after the roll must have the same color as that square. Rolling onto a white square has no such restriction. The cube must never roll onto a black square.

During the whole trip the cube may visit each chromatic square only once and any white square any number of times, and it may never visit a black square. The cube disappears when it visits the last chromatic square. The order in which the chromatic squares must be visited is known before the trip begins.

Given that order, find the least number of steps for the cube to visit all six chromatic squares in that order.

The input is a sequence of datasets. Each dataset has the form

w d
c(1,1) ... c(w,1)
...
c(1,d) ... c(w,d)
v1v2v3v4v5v6

The first line has two positive integers $w$ and $d$ separated by a space. The next $d$ lines are strings of $w$ characters with no spaces. Each character $c(i,j)$ is one of r, g, b, c, m, y, w, k (red, green, blue, cyan, magenta, yellow, white, black) or the sign #. Each of r, g, b, c, m, y and # occurs exactly once in a dataset. The last line is a six-character string $v_1v_2v_3v_4v_5v_6$, a permutation of "rgbcmy".

$w$ is the width (east-west length) and $d$ the depth (north-south length) of the bed, measured in squares; neither exceeds $30$. Character $c(1,1)$ is the north-west corner, $c(w,1)$ the north-east, $c(1,d)$ the south-west and $c(w,d)$ the south-east. A letter gives the color of that square; a # marks a white square that is the cube's starting position.

The string $v_1 \ldots v_6$ gives the order of colors to visit: the cube must visit the squares colored $v_1, v_2, \ldots, v_6$ in this order.

A line containing two zeros separated by a space ends the input.

For each dataset, print on its own line the least number of steps, or unreachable if no such trip exists.