장음계

음악에서 가청 주파수 범위는 옥타브로 나뉘며, 한 옥타브는 주파수가 서로 2배 이내인 구간을 뜻한다. 예를 들어 가온 C(middle C)는 약 263 Hz에 해당한다. 가온 C 아래 옥타브는 131.5 Hz부터 263 Hz까지, 위 옥타브는 263 Hz부터 526 Hz까지를 차지한다.

한 옥타브에는 13개의 반음계 음(chromatic note)이 있으며, 인접한 음들의 주파수는 일정한 비율로 커진다. 인접한 두 반음계 음 사이의 간격을 반음(semi-tone)이라 한다. 한 옥타브에는 반음이 12개 있으므로, 반음 하나의 주파수 비율은 약 $1.0593$이다(즉 $1.0593^{12} = 2$). 온음(tone)은 반음 두 개에 해당한다.

반음계의 음 이름은 전통에 따라 순서대로 C, C#, D, D#, E, F, F#, G, G#, A, A#, B로 부르고, 그 다음 다시 C로 돌아가 모든 옥타브에서 같은 이름을 반복한다.

서양 음악은 반음계의 모든 음을 쓰는 경우가 드물다. 대신 한 곡에서는 보통 13개 반음 중 8개만 사용하는데, 그중 가장 흔한 것이 장음계(major scale)다. 장음계의 8개 음은 순서대로 온음, 온음, 반음, 온음, 온음, 온음, 반음 간격으로 배치된다. 장음계는 어떤 반음계 음에서든 시작할 수 있으며, 그 시작음이 음계의 으뜸음, 즉 조(key)를 정한다. 예를 들어 C 조에서 장음계는 C, D, E, F, G, A, B, C이고, F 조에서는 F, G, A, A#, C, D, E, F이다.

음의 나열이 주어지면, 그 곡이 작곡되었을 수 있는 모든 조(key)를 찾아라. 나열된 모든 음이 어떤 조의 장음계에 속할 때에만, 그리고 그럴 때에만 그 조를 답으로 보고한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 공백으로 구분된 반음계 음들의 나열이 담긴 한 줄이다. 입력의 각 줄은 1000자를 넘지 않는다. END라는 단어가 적힌 줄은 입력의 끝을 나타내며, 테스트 케이스가 아니다.

각 테스트 케이스마다 가능한 모든 조를 C, C#, D, D#, E, F, F#, G, G#, A, A#, B 순서로 한 줄에 출력한다. 조와 조 사이는 공백 하나로 구분한다. 가능한 조가 없으면 빈 줄을 출력한다.