가희와 코드

가희의 오빠는 노래를 듣고 즉석에서 반주를 할 수 있습니다. 이번에도 가희는 새로운 노래를 듣고 가희만의 방식으로 반주를 하려고 합니다. 문제에서 등장하는 음의 이름은 12개입니다.

[표 1] 문제에 등장하는 12개의 음의 이름

음의 이름이 같아도 높이는 다를 수 있습니다. 높이는 옥타브로 정해집니다.

음에 대한 정보는 아래 두 형식 중 하나로 주어집니다.

• {character}{octave}: {octave} 옥타브에 있고 음의 이름이 {character}인 음입니다.
• {character}{octave}{additional_character}: {octave} 옥타브에 있고 음의 이름이 {character}{additional_character}인 음입니다. {additional_character}는 # 또는 $ 중 하나입니다.

즉, 음에 대한 정보는 옥타브와 음의 이름으로 이루어집니다. 그림 1은 피아노 건반을 나타내며, 오른쪽으로 갈수록 음이 높아집니다.

[그림 1] 0 옥타브의 음들과 대응되는 피아노 건반

두 음이 인접한다면 아래 조건 중 하나를 만족합니다.

• 같은 옥타브에 있는 경우: 음의 이름 n1의 순번 s1과 음의 이름 n2의 순번 s2의 차이가 1이면 두 음은 인접합니다. 순번은 표 1에 있습니다.
• {octave} 옥타브이고 음의 이름이 B인 음과 {octave}+1 옥타브이고 음의 이름이 C인 음은 인접합니다.

예를 들어 0 옥타브 C와 0 옥타브 C#은 첫 번째 조건을, 0 옥타브 B와 1 옥타브 C는 두 번째 조건을 만족합니다. 따라서 1 옥타브 C와 1 옥타브 C#, 0 옥타브 B와 1 옥타브 C는 인접합니다. 그림 2에서 빨간 화살표는 인접한 두 음을 보여줍니다.

[그림 2] 인접한 두 음의 예시

인접한 두 음 사이의 거리는 반음입니다. 음 note1과 음 note2의 반음 거리가 n이라는 것은 아래 둘 중 하나를 뜻합니다.

• note1보다 n개의 반음만큼 음이 높은 음이 note2입니다.
• note1보다 n개의 반음만큼 음이 낮은 음이 note2입니다.

표 2는 문제에 자주 나오는 용어와 그에 대응하는 반음 거리입니다.

[표 2] 문제에 자주 나오는 용어들과 대응되는 반음 거리

[그림 3] 0 옥타브 도 C0로부터 단 3도 위, 장 3도 위에 있는 음

그림 1에서 각 화살표는 반음 1개의 거리입니다. C0으로부터 단 3도 위에 있는 음은 D0#이고 음의 이름은 D#입니다. C0에서 출발하여 빨간색 화살표를 따라 이동하면 도착하는 음이기 때문입니다. C0으로부터 장 3도 위에 있는 음은 E0이고 음의 이름은 E입니다. C0에서 출발하여 빨간색 화살표와 보라색 화살표를 따라 이동하면 도착하는 음이기 때문입니다.

코드에서 근음(1음)은 뿌리가 되는 음을 뜻합니다. 근음 위에 장 3도를 쌓고, 그 위에 단 3도를 쌓아 만든 코드를 Major 코드라고 합니다. 표 3에 Major 코드의 예시가 있습니다.

[표 3] Major 코드 예시

Major 코드에서 3음을 반음 내린 것을 minor 코드라고 합니다. 표 4에 minor 코드의 예시가 있습니다.

[표 4] minor 코드 예시

Major 코드에서 5음을 반음 올린 것을 aug 코드라고 합니다. 표 5에 aug 코드의 예시가 있습니다.

[표 5] aug 코드 예시

Major 코드에서 3음과 5음을 각각 반음 내린 것을 dim 코드라고 합니다. 표 6에 dim 코드의 예시가 있습니다.

[표 6] dim 코드 예시

가희는 아래와 같은 알고리즘으로 반주를 하려고 합니다.

• 이전 p개의 마디에서 k번 이상 쓰였던 코드들은 제외합니다. 이 작업을 수행한 후 남은 코드의 개수가 r이라면,
  • r이 0이면, 가장 오랫동안 사용하지 않은 코드를 선택합니다. 그러한 코드가 여러 개 있다면, 아스키코드 사전 순으로 가장 앞에 있는 것을 선택합니다.
  • r이 0보다 크면, 코드를 이루는 음의 이름이 m번째 마디에 총 몇 번 나왔는지 계산합니다. 이 수치가 가장 높은 코드를 선택합니다. 그러한 코드가 여러 개인 경우, 아스키코드 사전 순으로 가장 앞선 코드를 선택합니다.

첫 줄에 마디 수 m과 문제에서 설명한 p, k가 공백으로 구분되어 주어집니다.

다음 m개의 줄에 마디에 나오는 음의 정보가 주어집니다. 음은 아래 형식으로 주어집니다.

{character}{octave}{additional_character}

• {character}: A, B, C, D, E, F, G 중 하나입니다. 한국식 음의 이름은 각각 라, 시, 도, 레, 미, 파, 솔을 의미합니다.
• {octave}: -2 이상 7 이하의 정수입니다.
• {additional_character} (선택): {character}{octave}보다 반음 높으면 #, 반음 낮으면 $으로 주어집니다. 이때 해당 음에서만 반음이 높아지거나 낮아집니다.

예를 들어 한 마디에 0 옥타브 레, -1 옥타브 시, 0 옥타브 레#, 0 옥타브 레♭이 있다면 입력은 다음과 같습니다.

D0B-1D0#D0$

또한 한 마디에 0 옥타브 레#, 0 옥타브 레, 0 옥타브 레#, 0 옥타브 레#이 있다면 입력은 다음과 같습니다.

D0#D0D0#D0#

아래 입력은 주어지지 않습니다.

[표 14] 주어지지 않는 입력

m개의 줄에 답을 출력합니다. 각 줄은 아래 형식으로 출력합니다.

{character}{additional_character}{type}

• {character}: A, B, C, D, E, F, G 중 하나입니다. 한국식 음의 이름은 각각 라, 시, 도, 레, 미, 파, 솔을 의미합니다.
• {additional_character} (선택): 근음이 {character}보다 반음 위에 있으면 #을 출력합니다. 다만 {character}가 B이거나 E이면 #을 붙이지 않습니다. #을 붙이면 그 음만 반음이 높아집니다.
• {type}: 문제에 제시된 M, m, aug, dim 중 하나입니다.

예를 들어 D#M은 E$M으로도 표시될 수 있습니다. 같은 옥타브에서 음의 이름이 D#인 음과 E$인 음은 같은 음(딴이름 한소리)이기 때문입니다. 이로 인한 혼동을 막으려고 출력 형식에 제한을 두었습니다.

• $1 \le m \le 5 \times 10^4$
• $1 \le p \le m$
• $1 \le k \le p$
• 주어지는 음의 총개수는 50만을 넘지 않습니다.
• 각각의 마디에는 최소 하나 이상의 음이 있습니다.
• 조표에 아무것도 붙지 않았다고 가정합니다.
• 문제에 나오지 않는 요소(제자리표, 겹올림, 겹내림, 붙임줄, 이음줄)는 모두 무시합니다.

오빠. 숨어서 듣지 말고 대놓고 듣자.