Magic Pyramid

The famous Rubik's Cube puzzle has many variants. One of them, the Magic Pyramid, is built on a tetrahedron instead of a cube. The four faces of the tetrahedron are labeled X, U, V, and W, and each face is divided into 9 equilateral triangles. The small triangles are numbered from 1 to 36 as shown in Figure 1. To assemble the tetrahedron, fold the big triangle along the internal thick lines and glue together the matching halves of the external thick lines.

Figure 1

Every small triangle is painted in one of four colors, written a, b, c, and d. Exactly 9 triangles carry each color.

You can transform the tetrahedron with the operation "rotate a face". First choose a face and orient the pyramid so that the chosen face is towards you. Then pick a direction, clockwise or counter-clockwise. Finally turn the part of the tetrahedron closest to the chosen face, the part whose thickness is 1/3 of the height of the tetrahedron, by 120 degrees in that direction, and leave the rest of the tetrahedron where it is. Figure 2 shows the effect of rotating face U clockwise.

Figure 2

Besides rotating a face you can also apply the operation "magic re-paint". This operation is defined by a permutation $p_1, \ldots, p_{36}$ of the integers 1 to 36. Applying it re-paints the triangle currently in position $i$ into the color of the triangle currently in position $p_i$. Positions are numbered as in Figure 1, and all 36 triangles are re-painted at the same time.

A single move is therefore one of 9 choices: turning one of the four faces clockwise or counter-clockwise, which is 8 choices, or the magic re-paint.

The puzzle is solved once some sequence of moves leaves all triangles on each face of the tetrahedron with the same color.

Write a program that finds the smallest number of moves that solves the Magic Pyramid. Every puzzle given in the input can be solved in 9 moves or fewer.

The first line contains 36 letters from a to d with no spaces. The $i$-th letter is the initial color of triangle number $i$. Each of the four letters occurs exactly 9 times.

The second line contains 36 distinct integers describing the magic re-paint operation. The $i$-th integer is the member $p_i$ of the permutation that defines the operation, and it is between 1 and 36.

Print the smallest number of moves that solves the puzzle. Print 0 if each of the four faces already has a single color.

The colors of the triangles are drawn with these patterns.

Figure 3 shows the coloring of the first example, and Figures 4 and 5 show the result of applying one move each. That example is solved by the magic re-paint followed by a counter-clockwise turn of face U, so the answer is 2.

Figure 3

Figure 4

Figure 5