Improvisation

Chris always dreamed of playing jazz. He has grown up but still cannot play a single instrument, so instead he wants to build a new kind of improvisation engine. His program, Improvisation, takes an improvisation that fits one chord progression and rewrites it so that it fits a different chord progression. Your task is to implement that algorithm.

A few definitions are needed first.

Notes. There are 12 notes, arranged in a fixed classical order:

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

The order is cyclic: B is followed by C again. Each of the five notes written with a sharp (#) can also be written with a flat (♭).

Pause. A pause is written as _.

Chords. Every chord has a mode and a prime. The prime is a single note. There are six modes: maj7, min7, dim, 7, 7♭9, and 7#9. Each mode defines a scale: a set $S \subseteq \{0, 1, \dots, 11\}$ of note offsets relative to the prime in the classical order. For example, if the prime is D and $S = \{0, 2, 4\}$, then the fitting notes are $\{D, E, F\#\}$. The scales are:

A chord is written as its prime and mode joined into one word (for example, Cmaj7). The fitting notes of Cmaj7 are $\{C, D, E, G, A, B\}$.

Improvisation. An improvisation is a finite sequence of notes and pauses.

Nearest fitting note. For a note $x$ and a chord $A$, the nearest note that fits is the first element of the sequence

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

that fits $A$, where $\text{next}(x)$ is the note right after $x$ in the classical order and $\text{prev}(x)$ is the note right before it.

The algorithm takes a chord progression $P$ of length $m$ and an improvisation $I$ of length $n$, and produces a new improvisation $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

Read a chord progression and an improvisation, run the algorithm, and print the resulting improvisation $J$.

The first line contains one integer $m$ ($1 \le m \le 100000$). The second line contains $m$ chords separated by single spaces. The third line contains one integer $n$ ($1 \le n \le 100000$). The fourth line contains $n$ notes and/or pauses separated by single spaces, forming the improvisation.

In the input a sharp is written as # and a flat as the lowercase letter b: for example G♭ is written Gb, and the modes 7♭9 and 7#9 are written 7b9 and 7#9. A pause is _.

Print one line with $n$ notes and/or pauses separated by single spaces: the resulting improvisation $J$.

When a note has two spellings (a sharp note), print it using the spelling implied by the chord $P[p]$ that produced it on line 5 of the algorithm. If that chord's prime is written with a flat, use the flat spelling; otherwise use the sharp spelling. As in the input, a sharp is # and a flat is b.