Minor Setback

Time limit3sMemory limit1024 MB

Summary

Given N tuned frequencies, find the single major or minor key that fits all of them, then print each pitch's name in that key.

Level: Medium4 of 10
Topics: Math, Implementation, Brute force
Solved: No attempts yet

Problem

Some Music Theory

Musical pitches are described by frequencies on 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 the pitches used in Western music and their frequencies.

Table 1: Frequencies and 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 a pitch's frequency yields the same pitch one octave higher. Both $440$ and $880\ \textrm{Hz}$ are $\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.

Input

The first line 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$ , one pitch frequency, with at most $8$ digits after the decimal point. You may assume the instrument was in tune, so each frequency approximates $440\cdot 2^{a/12}$ for some integer $a$ with absolute error at most $10^{-4}$ .

Output

On the first line, print the name of the key the song was played in, such as G major or F# minor. Pitch names follow the format below. If the song fits none of the keys in Table 2, or if more than one key could fit, print cannot determine key.

If the key cannot be determined, print nothing else. Otherwise, print $N$ lines, each with one pitch name in input order. A pitch name is a letter from A to G, optionally followed by # for sharp or b for flat. A pitch can have several names, but for each key only the name listed in its allowed-pitches column is used. For example, in $\textrm{F}^{\sharp }$ minor, print C# and not Db.

Examples2

Example 1

Input

7
783.9908720
783.9908720
587.3295358
587.3295358
659.2551138
659.2551138
587.3295358

Expected output

cannot determine key

Example 2

Input

5
523.2511306
391.9954360
440.0
329.6275569
369.9944227

Expected output

G major
C
G
A
E
F#