즉흥 연주

크리스는 늘 재즈 연주를 꿈꿔 왔습니다. 어른이 되었지만 여전히 악기를 하나도 다루지 못하는 그는, 대신 새로운 즉흥 연주 엔진을 만들기로 했습니다. 그의 프로그램 Improvisation 은 어떤 코드 진행에 어울리는 즉흥 연주를 받아, 다른 코드 진행에 어울리도록 바꿔 줍니다. 이 알고리즘을 구현하세요.

먼저 몇 가지 개념이 필요합니다.

음(note). 음은 모두 12개이며, 고정된 기본(classical) 순서 로 배열됩니다.

C, C#(D♭), D, D#(E♭), E, F, F#(G♭), G, G#(A♭), A, A#(B♭), B

이 순서는 순환합니다. 즉 B 다음에는 다시 C가 옵니다. 샤프(#)로 적는 다섯 개의 음은 플랫(♭)으로도 적을 수 있습니다.

쉼표(pause). 쉼표는 _ 로 나타냅니다.

코드(chord). 모든 코드는 모드(mode) 와 프라임(prime) 을 가집니다. 프라임은 하나의 음입니다. 모드는 maj7, min7, dim, 7, 7♭9, 7#9 의 여섯 가지입니다. 각 모드는 스케일(scale), 즉 기본 순서에서 프라임을 기준으로 한 음 오프셋들의 집합 $S \subseteq \{0, 1, \dots, 11\}$ 을 정의합니다. 예를 들어 프라임이 D이고 $S = \{0, 2, 4\}$ 이면, 어울리는 음은 $\{D, E, F\#\}$ 입니다. 각 모드의 스케일은 다음과 같습니다.

코드는 프라임과 모드를 한 단어로 붙여 적습니다(예: Cmaj7). Cmaj7 에 어울리는 음은 $\{C, D, E, G, A, B\}$ 입니다.

즉흥 연주(improvisation). 즉흥 연주는 음과 쉼표로 이루어진 유한 수열입니다.

가장 가까운 어울리는 음. 음 $x$ 와 코드 $A$ 에 대해, 가장 가까운 어울리는 음 은 다음 수열

$x,\ \text{next}(x),\ \text{prev}(x),\ \text{next}(\text{next}(x)),\ \text{prev}(\text{prev}(x)),\ \dots$

에서 $A$ 에 어울리는 첫 번째 원소입니다. 여기서 $\text{next}(x)$ 는 기본 순서에서 $x$ 바로 다음 음, $\text{prev}(x)$ 는 바로 앞 음입니다.

알고리즘은 길이 $m$ 인 코드 진행 $P$ 와 길이 $n$ 인 즉흥 연주 $I$ 를 입력받아, 새로운 즉흥 연주 $J$ 를 만듭니다.

 1  J := sequence of length n containing only pauses
 2  p := 1
 3  for i := 1 to n do begin
 4      if I[i] <> pause then begin
 5          J[i] := nearest note to I[i] which fits to P[p]
 6          if i mod 4 = 0 then begin
 7              p := p + 1
 8              if p > m then p := 1
 9          end
10      end
11  end

코드 진행과 즉흥 연주를 읽어 이 알고리즘을 수행한 뒤, 그 결과인 즉흥 연주 $J$ 를 출력하세요.

첫째 줄에 정수 $m$ ($1 \le m \le 100000$) 이 주어집니다. 둘째 줄에는 코드 $m$ 개가 공백 하나로 구분되어 주어집니다. 셋째 줄에 정수 $n$ ($1 \le n \le 100000$) 이 주어집니다. 넷째 줄에는 즉흥 연주를 이루는 음과 쉼표 $n$ 개가 공백 하나로 구분되어 주어집니다.

입력에서 샤프는 #, 플랫은 소문자 b 로 적습니다. 예를 들어 G♭ 은 Gb, 모드 7♭9 와 7#9 는 각각 7b9, 7#9 로 적습니다. 쉼표는 _ 입니다.

한 줄에, 결과 즉흥 연주 $J$ 를 이루는 음과 쉼표 $n$ 개를 공백 하나로 구분하여 출력하세요.

두 가지로 적을 수 있는 음(샤프 음)을 출력할 때는, 그 음을 만든 코드(알고리즘 5번 줄의 $P[p]$)에 따라 표기를 정합니다. 그 코드의 프라임이 플랫으로 적혀 있으면 플랫 표기를, 그렇지 않으면 샤프 표기를 사용합니다. 입력과 마찬가지로 샤프는 #, 플랫은 b 입니다.