Major Scales

Time limit1sMemory limit128 MB

Summary

For each sequence of notes, list the keys whose major scale contains every note, ordered C through B.

Level: Easy3 of 10
Topics: Implementation, String, Brute force, Hash map
Solved: No attempts yet

Problem

In music, the range of audible frequencies is divided into octaves, where each octave spans frequencies within a factor of 2 of one another. For example, the note called middle C corresponds to a frequency of 263 Hz. The octave below middle C spans 131.5 Hz to 263 Hz, while the octave above middle C spans 263 Hz to 526 Hz.

An octave contains 13 chromatic notes whose frequencies differ by a common ratio. The separation between two adjacent chromatic notes is called a half-step or semi-tone. There are 12 semi-tones in an octave, so the frequency ratio of one semi-tone is about $1.0593$ (since $1.0593^{12} = 2$ ). A tone equals two semi-tones.

By historical tradition we name the notes of the chromatic scale, in order: C, C#, D, D#, E, F, F#, G, G#, A, A#, B, and then C again, repeating the same names in every octave.

Western music rarely uses all of the chromatic notes. Instead, 8 of the 13 chromatic notes are commonly used in a composition. The most common such set is the major scale. The 8 notes of a major scale, in order, are separated by: tone, tone, semi-tone, tone, tone, tone, semi-tone. A major scale may begin on any chromatic note; that starting note defines the key of the scale. For example, in the key of C the major scale is C, D, E, F, G, A, B, C; in the key of F it is F, G, A, A#, C, D, E, F.

Given a sequence of notes, identify every key in which the music might have been written. Report a key if and only if every note in the sequence belongs to the major scale of that key. Your program needs no musical ear.

Input

The input contains several test cases. Each test case is a single line containing a sequence of chromatic notes separated by whitespace. No input line exceeds 1000 characters. The line containing the word END marks the end of input and is not a test case.

Output

For each test case, output one line listing every possible key, in the order C, C#, D, D#, E, F, F#, G, G#, A, A#, B. Separate the keys with a single space. If no key is possible, output an empty line.

Examples3

Example 1

Input

C C D F E G A A F G B
A B C D E F G C#
C C D F E G A A F G
C C C C C
END

Expected output

C

C F
C C# D# F G G# A#

Example 2
Input
```
F G A A# C D E
END
```
Expected output
```
F
```
Example 3
Input
```
G A B C D E F#
END
```
Expected output
```
G
```