마술 피라미드

유명한 루빅스 큐브 퍼즐에는 변형이 많다. 그중 하나인 마술 피라미드는 정육면체 대신 정사면체를 쓴다. 정사면체의 네 면에는 X, U, V, W라는 이름이 붙어 있고, 각 면은 정삼각형 9개로 나뉜다. 작은 삼각형에는 그림 1처럼 1번부터 36번까지 번호가 매겨져 있다. 정사면체를 조립하려면 큰 삼각형을 안쪽 굵은 선을 따라 접고, 바깥쪽 굵은 선에서 서로 맞닿는 절반끼리 붙이면 된다.

그림 1

작은 삼각형은 각각 a, b, c, d로 나타내는 네 가지 색 중 하나로 칠해져 있고, 색마다 정확히 9개씩 있다.

정사면체는 "면 돌리기" 연산으로 바꿀 수 있다. 먼저 면 하나를 골라 그 면이 자기 쪽을 향하도록 정사면체를 놓는다. 다음으로 회전 방향을 시계 방향과 반시계 방향 중에서 정한다. 마지막으로 고른 면에서 가장 가깝고 두께가 정사면체 높이의 1/3인 부분을 정한 방향으로 120도 돌리고, 나머지 부분은 그대로 둔다. 그림 2는 면 U를 시계 방향으로 돌린 결과다.

그림 2

면 돌리기 말고 "마술 재도색" 연산도 쓸 수 있다. 이 연산은 1부터 36까지의 순열 $p_1, \ldots, p_{36}$으로 정의한다. 연산을 적용하면 지금 $i$번 자리에 있는 삼각형이 지금 $p_i$번 자리에 있는 삼각형의 색으로 칠해진다. 자리 번호는 그림 1의 번호를 그대로 쓰고, 삼각형 36개가 동시에 칠해진다.

한 번의 이동으로 고를 수 있는 선택은 모두 9가지다. 네 면 중 하나를 시계 방향이나 반시계 방향으로 돌리는 8가지와 마술 재도색 1가지다.

이동을 몇 번 적용해서 정사면체의 각 면이 한 가지 색으로만 이루어지면 퍼즐이 풀린 것이다.

마술 피라미드를 푸는 데 필요한 이동의 최소 횟수를 구하는 프로그램을 작성하시오. 입력으로 주어지는 퍼즐은 모두 9번 이하의 이동으로 풀 수 있다.

첫째 줄에 a부터 d까지의 문자 36개가 공백 없이 주어진다. $i$번째 문자는 $i$번 삼각형의 처음 색이다. 네 문자는 각각 정확히 9번씩 나온다.

둘째 줄에 마술 재도색 연산을 나타내는 서로 다른 정수 36개가 주어진다. $i$번째 정수가 연산을 정의하는 순열의 원소 $p_i$이고, 1 이상 36 이하다.

첫째 줄에 퍼즐을 푸는 데 필요한 이동의 최소 횟수를 출력한다. 처음부터 네 면이 각각 한 가지 색이면 0을 출력한다.

작은 삼각형의 색은 다음 무늬로 나타낸다.

그림 3은 첫 번째 예제의 처음 색칠 상태이고, 그림 4와 그림 5는 이동을 하나씩 적용한 결과다. 이 예제는 마술 재도색을 적용한 다음 면 U를 반시계 방향으로 돌리면 풀리므로 답은 2다.

그림 3

그림 4

그림 5