Minor Setback

/problems/minorsetback/file/statement/en/img-0001.jpg
Photo by Xato

You are developing a smartphone app that converts audio recorded from an instrument into sheet music. You already have the code to record the audio and convert it into sequence of frequency values. What is left is to translate those frequencies into pitch names more easily recognizable to musicians.

Some Music Theory

Musical pitches are described by frequencies using a logarithmic scale. The frequency $440\ \textrm{Hz}$ corresponds to the pitch named $\textrm{A}$. Multiplying a pitch’s frequency by $\sqrt [12]{2}$ produces the next higher pitch. Table 1 lists pitches used in Western music and their frequencies.

Table 1: Frequencies and corresponding pitch names of various notes.

frequency (Hz)

pitch name

frequency (Hz)

pitch name

$440$

$\textrm{A}$

$440 \cdot 2^{6/12} \approx 622.25$

$\textrm{D}^{\sharp }$, $\textrm{E}^{\flat }$

$440 \cdot 2^{1/12} \approx 466.16$

$\textrm{A}^{\sharp }$, $\textrm{B}^{\flat }$

$440 \cdot 2^{7/12} \approx 659.26$

$\textrm{E}$

$440 \cdot 2^{2/12} \approx 493.88$

$\textrm{B}$

$440 \cdot 2^{8/12} \approx 698.46$

$\textrm{F}$

$440 \cdot 2^{3/12} \approx 523.25$

$\textrm{C}$

$440 \cdot 2^{9/12} \approx 739.99$

$\textrm{F}^{\sharp }$, $\textrm{G}^{\flat }$

$440 \cdot 2^{4/12} \approx 554.37$

$\textrm{C}^{\sharp }$, $\textrm{D}^{\flat }$

$440 \cdot 2^{10/12} \approx 783.99$

$\textrm{G}$

$440 \cdot 2^{5/12} \approx 587.33$

$\textrm{D}$

$440 \cdot 2^{11/12} \approx 830.61$

$\textrm{G}^{\sharp }$, $\textrm{A}^{\flat }$

   

$880$

$\textrm{A}$

Doubling any pitch’s frequency yields the same pitch, but one octave higher (note that both $440$ and $880\ \textrm{Hz}$ correspond to pitch $\textrm{A}$). This rule generalizes: multiplying $554.37\ \textrm{Hz}$ by a power of two yields another $\textrm{C}^{\sharp }$. Some pitches have multiple names, as shown in the table.

Your Task

You have a song, represented as a sequence of frequencies. Songs in a musical key typically contain only a subset of the possible pitches. Assume that the given song is in one of the common keys listed in Table 2. First, determine what key the song is in. Then, translate the song into a sequence of pitch names.

Table 2: A few musical keys and the pitches they use.

key name

allowed pitches

key name

allowed pitches

$\textrm{G}$ major

$\textrm{G}$, $\textrm{A}$, $\textrm{B}$, $\textrm{C}$, $\textrm{D}$, $\textrm{E}$, and $\textrm{F}^{\sharp }$

$\textrm{F}^{\sharp }$ minor

$\textrm{F}^{\sharp }$, $\textrm{G}^{\sharp }$, $\textrm{A}$, $\textrm{B}$, $\textrm{C}^{\sharp }$, $\textrm{D}$, and $\textrm{E}$

$\textrm{C}$ major

$\textrm{C}$, $\textrm{D}$, $\textrm{E}$, $\textrm{F}$, $\textrm{G}$, $\textrm{A}$, and $\textrm{B}$

$\textrm{G}$ minor

$\textrm{G}$, $\textrm{A}$, $\textrm{B}^{\flat }$, $\textrm{C}$, $\textrm{D}$, $\textrm{E}^{\flat }$, and $\textrm{F}$

$\textrm{E}^{\flat }$ major

$\textrm{E}^{\flat }$, $\textrm{F}$, $\textrm{G}$, $\textrm{A}^{\flat }$, $\textrm{B}^{\flat }$, $\textrm{C}$, and $\textrm{D}$

Input

The first line of input contains a single integer $1 \leq N \leq 100\, 000$, the number of frequencies in the song. The next $N$ lines each contain a real number $20 \le f \le 4\, 000$, representing one pitch frequency, with at most $8$ digits after the decimal point. You may assume that the song was played using an instrument that is in tune, so that each frequency represents a valid pitch: each frequency approximates $440\cdot 2^{a/12}$ for some integer $a$ with absolute error at most $10^{-4}$.

Output

On the first line, output the name of the key that the song was played in: G major, F# minor, etc. See below for instructions for how to format pitch names. If the song does not fit any of the keys in Table 2, or if multiple possible keys could fit the song, print cannot determine key.

If the key could not be determined, print no further output. Otherwise, print $N$ lines, each containing one pitch name (in the order of the input sequence). Each pitch name should be a letter A through G followed optionally by a second character, either # or b, indicating a sharp or flat. Note that although pitches can have multiple names, only one of these names is listed in the allowed-pitches table for any given key, and this is the name you should use. For example, print C#, and not Db, when writing pitches for the key $\textrm{F}^{\sharp }$ minor.

Sample Input 1 Sample Output 1
7
783.9908720
783.9908720
587.3295358
587.3295358
659.2551138
659.2551138
587.3295358
cannot determine key
Sample Input 2 Sample Output 2
5
523.2511306
391.9954360
440.0
329.6275569
369.9944227
G major
C
G
A
E
F#