시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 21 11 8 88.889%

문제

음악 용어에서 ‘음계’는 음을 낮은 음부터 높은 음 순으로 나열한 음의 층계이다. ‘음정’은 두 음 사이의 거리를 말한다. 서양 음악에서 한 옥타브는 12음계 {A, A#, B, C, C#, D, D#, E, F, F#, G, G#} 로 구성된다.

피아노 건반에서 한 옥타브 내에는 흰 건반 7개, 검은 건반 5개, 총 12개 건반이 있으며 인접한 두 건반의 음정은 항상 ‘반음’이다. ‘#’는 음을 반음 높였다는 의미이다. 위 피아노 건반 그림을 보면 맨왼쪽 C0부터 시작하여 낮은 음에서 높은 순으로 건반들이 나열되어 있다.

옥타브는 0옥타브부터 시작하는데, 가령 C2는 2옥타브의 C음이고, A8#은 8옥타브 A음을 반음 높인 것이다. 따라서 C0에서 C1은 12반음이고, B0에서 E1은 5반음이다. 현대의 표준적인 피아노에는 흰 건반 52개, 검은 건반 36개로 총 88개의 건반이 있다. 그 음역은 A0부터 C8까지이다. 그러나 이번 문제에서는 피아노 건반이 C0부터 시작하여 음이 높아지는 방향으로 무한히 이어진다고 가정한다.

민정이는 요즘 왼손 검지와 오른손 검지, 두 손가락만으로 칠 수 있는 단순한 피아노 악보들을 연주하고 있다. 민정이는 연주할 때 가능한 한 손가락 이동을 적게 하고 싶어 한다. 이때 손가락 이동 거리는 두 음의 음정으로 결정하기로 했다.

예를 들어, 왼손 검지와 오른손 검지가 건반 상에서 각각 C0와 A0 위에 있고 다음 음으로 G0을 쳐야 한다고 하자. C0와 G0가 7반음이므로 왼손 검지로 친다면 7만큼 이동한다. 한편 A0와 G0는 2반음이므로 오른손 검지로 친다면 2만큼 이동한다.

민정이는 연주 시 하나의 음을 반드시 하나의 손가락으로 연주한다. 두 손가락은 서로 엇갈려 위치할 수 있으나 악보 상에서 두 음 이상을 동시에 누르는 경우는 없으며 항상 순차적으로 한 음씩 연주한다. 악보를 연주하는데 무리가 없을 정도로 팔이 충분히 길다고 가정한다.

처음 두 손가락의 건반 상 위치와 피아노 악보가 주어질 때, 민정이가 악보를 완주하기 위해 두 손가락이 이동 해야 하는 거리의 최솟값을 구하는 프로그램을 작성하라.

입력

입력은 세 줄로 이루어진다.

첫 번째 줄에 초기에 왼손 검지와 오른손 검지가 위치한 건반 위의 음이 차례대로 공백으로 구분되어 주어진다. 이때 두 음의 음정은 1 이상이다.

두 번째 줄에는 양의 정수 N이 주어진다.

세 번째 줄에는 악보가 주어지는데, N개의 음들이 순서대로 공백으로 구분되어 주어진다.

출력

첫째 줄에 악보를 완주하기 위해 두 손가락이 이동한 총 거리를 출력한다. 둘째 줄에 N개의 음을 연주한 방법을 공백으로 구분하여 출력한다. i(1 ≤ i ≤ N)번 째 음을 왼손 검지로 누른 경우 1을, 오른손 검지로 누른 경우 2를 출력한다.

제한

음은 Xy 또는 Xy# 형식의 2이상 3이하의 문자열로 주어진다. 여기서 X는 'A'부터 'G' 사이의 알파벳 대문자 중 하나이고, y는 음이 아닌 정수이다. (0 ≤ y ≤ 9)

서브태스크 1 (20점)

  • 1 ≤ ≤ 20

서브태스크 2 (80점)

  • 1 ≤ N ≤ 1,000

예제 입력 1

C0 A0
3
G0 E0# B0#

예제 출력 1

11
2 2 2

예제 입력 1에서 E0#과 B0#은 각각 F0, C1과의 음정이 0이다.

세 음 모두 오른손 검지로 칠 경우 2 + 2 + 7 = 11만큼 이동하며 이동 거리를 이보다 작게 만들 수는 없다.

예제 입력 2

C1# G0
2
G0 C1#

예제 출력 2

0
2 1

예제 입력 3

A0 B0
4
C1 D1# C1# A0#

예제 출력 3

7
2 2 2 1

채점

  • 예제는 채점하지 않는다.