시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1427 345 282 24.780%

문제

현환이는 음악 학원에서 피아노를 배우고 있다. 어느 날 선생님은 현환이에게 조표가 없는 악보를 주었다. 자 이제 어떤 음계가 사용되었는지 알아보려고 한다. 현환이는 피아노를 배운지 얼마 되지 않았기 때문에, 칠 수 있는 음계는 가단조와 다장조밖에 없다.

현대 음악에서 한 옥타브는 12음 {A, A#, B, C, C#, D, D#, E, F, F#, G, G#}으로 이루어진다. 가단조를 구성하는 음의 순서는 (A, B, C, D, E, F, G)이고, 다장조를 구성하는 음의 순서는 (C, D, E, F, G, A, B)이다.

가단조와 다장조를 구성하는 음은 같다. 그럼 차이는 무엇일까?

첫 번째 차이는 중심음의 차이이다. 으뜸음은 음계에서 가장 첫 번째 위치에 있는 음이고, 버금딸림음은 네 번째 위치에 있는 음이다. 마지막으로 딸림음은 다섯 번째 위치에 있는 음이다. 가단조에서 으뜸음, 버금딸림음, 딸림음은 A, D, E이고, 다장조에서는 C, F, G이다. 이 세 음을 중심음이라고 한다.

두 번째 차이는 음정의 차이이다. 가단조에서 세 번째 음(C)은 으뜸음(A)보다 반음 세 개 높고, 다장조에서 세 번째 음(E)은 으뜸음(C)보다 반음 네 개 높다. 이러한 음정의 차이때문에 단조는 슬픈 느낌을, 장조는 기쁜 느낌을 준다.

가단조 또는 다장조의 음악이 주어졌을 때, 어떤 음계인지 알아내는 프로그램을 작성하시오.

각 마디의 첫 음으로 나오는 중심음이 가장 많은 음계가 그 음악의 음계이다. 가단조와 다장조의 중심음 개수가 같은 경우에는 마지막 음으로 음계를 결정한다. 마지막 음은 가단조인 경우 A, D, 또는 E로 주어지며, 다장조인 경우 C, F 또는 G로 주어진다.

예를 들어, 유명한 음악인 Frère Jacques의 악보는 다음과 같다.

CD|EC|CD|EC|EF|G|EF|G|GAGF|EC|GAGF|EC|CG|C|CG|C

|는 각 마디를 나누는 마디선이다. 여기서 각 마디의 첫 번째 음을 적어보면 다음과 같다. (C, E, C, E, E, G, E, G, G, E, G, E, C, C, C, C) 여기서 (C, C, G, G, G, G, C, C, C, C)는 다장조의 중심음이고, (E, E, E, E, E, E)는 가단조의 중심음이다. 따라서, 이 음악은 다장조이다.

입력

첫째 줄에 음악이 주어진다. 음악은 {"A", "B", "C", "D", "E", "F", "G", "|"}로 이루어져 있으며, 길이는 5보다 크거나 같고, 100을 넘지 않는다. |가 연속해서 등장하거나, 문자열의 양쪽 끝에 나오는 경우는 없다.

출력

다장조라면 C-major, 가단조라면 A-minor를 출력한다. 항상 둘 중 하나로 답이 결정되는 입력만 주어진다.

예제 입력 1

CD|EC|CD|EC|EF|G|EF|G|GAGF|EC|GAGF|EC|CG|C|CG|C

예제 출력 1

C-major
W3sicHJvYmxlbV9pZCI6IjUyMTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWIyZThcdWM4NzBcdWM2NDAgXHViMmU0XHVjN2E1XHVjODcwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ2MDRcdWQ2NThcdWM3NzRcdWIyOTQgXHVjNzRjXHVjNTQ1IFx1ZDU1OVx1YzZkMFx1YzVkMFx1YzExYyBcdWQ1M2NcdWM1NDRcdWIxNzhcdWI5N2MgXHViYzMwXHVjNmIwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNWI0XHViMjkwIFx1YjBhMCBcdWMxMjBcdWMwZGRcdWIyZDhcdWM3NDAgXHVkNjA0XHVkNjU4XHVjNzc0XHVjNWQwXHVhYzhjIFx1Yzg3MFx1ZDQ1Y1x1YWMwMCBcdWM1YzZcdWIyOTQgXHVjNTQ1XHViY2Y0XHViOTdjIFx1YzhmY1x1YzVjOFx1YjJlNC4gXHVjNzkwIFx1Yzc3NFx1YzgxYyBcdWM1YjRcdWI1YTQgXHVjNzRjXHVhY2M0XHVhYzAwIFx1YzBhY1x1YzZhOVx1YjQxOFx1YzVjOFx1YjI5NFx1YzljMCBcdWM1NGNcdWM1NDRcdWJjZjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQ2MDRcdWQ2NThcdWM3NzRcdWIyOTQgXHVkNTNjXHVjNTQ0XHViMTc4XHViOTdjIFx1YmMzMFx1YzZiNFx1YzljMCBcdWM1YmNcdWI5YzggXHViNDE4XHVjOWMwIFx1YzU0YVx1YzU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1Y2U2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Yzc0Y1x1YWNjNFx1YjI5NCBcdWFjMDBcdWIyZThcdWM4NzBcdWM2NDAgXHViMmU0XHVjN2E1XHVjODcwXHViYzE2XHVjNWQwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjA0XHViMzAwIFx1Yzc0Y1x1YzU0NVx1YzVkMFx1YzExYyBcdWQ1NWMgXHVjNjI1XHVkMGMwXHViZTBjXHViMjk0IDEyXHVjNzRjIHtBLCBBIywgQiwgQywgQyMsIEQsIEQjLCBFLCBGLCBGIywgRywgRyN9XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAwXHViMmU4XHVjODcwXHViOTdjIFx1YWQ2Y1x1YzEzMVx1ZDU1OFx1YjI5NCBcdWM3NGNcdWM3NTggXHVjMjFjXHVjMTFjXHViMjk0IChBLCBCLCBDLCBELCBFLCBGLCBHKVx1Yzc3NFx1YWNlMCwgXHViMmU0XHVjN2E1XHVjODcwXHViOTdjIFx1YWQ2Y1x1YzEzMVx1ZDU1OFx1YjI5NCBcdWM3NGNcdWM3NTggXHVjMjFjXHVjMTFjXHViMjk0IChDLCBELCBFLCBGLCBHLCBBLCBCKVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHViMmU4XHVjODcwXHVjNjQwIFx1YjJlNFx1YzdhNVx1Yzg3MFx1Yjk3YyBcdWFkNmNcdWMxMzFcdWQ1NThcdWIyOTQgXHVjNzRjXHVjNzQwIFx1YWMxOVx1YjJlNC4gXHVhZGY4XHViN2ZjIFx1Y2MyOFx1Yzc3NFx1YjI5NCBcdWJiMzRcdWM1YzdcdWM3N2NcdWFlNGM/PFwvcD5cclxuXHJcbjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjYzI4XHVjNzc0XHViMjk0IFx1YzkxMVx1YzJlY1x1Yzc0Y1x1Yzc1OCBcdWNjMjhcdWM3NzRcdWM3NzRcdWIyZTQuIFx1YzczY1x1YjczOFx1Yzc0Y1x1Yzc0MCBcdWM3NGNcdWFjYzRcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjNzA0XHVjZTU4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM3NGNcdWM3NzRcdWFjZTAsIFx1YmM4NFx1YWUwOFx1YjUzOFx1YjliY1x1Yzc0Y1x1Yzc0MCBcdWIxMjQgXHViYzg4XHVjOWY4IFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjNzRjXHVjNzc0XHViMmU0LiBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMgXHViNTM4XHViOWJjXHVjNzRjXHVjNzQwIFx1YjJlNFx1YzEyZiBcdWJjODhcdWM5ZjggXHVjNzA0XHVjZTU4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM3NGNcdWM3NzRcdWIyZTQuIFx1YWMwMFx1YjJlOFx1Yzg3MFx1YzVkMFx1YzExYyBcdWM3M2NcdWI3MzhcdWM3NGMsIFx1YmM4NFx1YWUwOFx1YjUzOFx1YjliY1x1Yzc0YywgXHViNTM4XHViOWJjXHVjNzRjXHVjNzQwIEEsIEQsIEVcdWM3NzRcdWFjZTAsIFx1YjJlNFx1YzdhNVx1Yzg3MFx1YzVkMFx1YzExY1x1YjI5NCBDLCBGLCBHXHVjNzc0XHViMmU0LiBcdWM3NzQgXHVjMTM4IFx1Yzc0Y1x1Yzc0NCBcdWM5MTFcdWMyZWNcdWM3NGNcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1Y2MyOFx1Yzc3NFx1YjI5NCBcdWM3NGNcdWM4MTVcdWM3NTggXHVjYzI4XHVjNzc0XHVjNzc0XHViMmU0LiBcdWFjMDBcdWIyZThcdWM4NzBcdWM1ZDBcdWMxMWMgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWM3NGMoQylcdWM3NDAgXHVjNzNjXHViNzM4XHVjNzRjKEEpXHViY2Y0XHViMmU0IFx1YmMxOFx1Yzc0YyBcdWMxMzggXHVhYzFjIFx1YjE5Mlx1YWNlMCwgXHViMmU0XHVjN2E1XHVjODcwXHVjNWQwXHVjMTFjIFx1YzEzOCBcdWJjODhcdWM5ZjggXHVjNzRjKEUpXHVjNzQwIFx1YzczY1x1YjczOFx1Yzc0YyhDKVx1YmNmNFx1YjJlNCBcdWJjMThcdWM3NGMgXHViMTI0IFx1YWMxYyBcdWIxOTJcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWM3NGNcdWM4MTVcdWM3NTggXHVjYzI4XHVjNzc0XHViNTRjXHViYjM4XHVjNWQwIFx1YjJlOFx1Yzg3MFx1YjI5NCBcdWMyYWNcdWQ1MDgmbmJzcDtcdWIyOTBcdWIwOGNcdWM3NDQsIFx1YzdhNVx1Yzg3MFx1YjI5NCBcdWFlMzBcdWMwNWMgXHViMjkwXHViMDhjXHVjNzQ0IFx1YzkwMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHViMmU4XHVjODcwIFx1YjYxMFx1YjI5NCBcdWIyZTRcdWM3YTVcdWM4NzBcdWM3NTggXHVjNzRjXHVjNTQ1XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzViNFx1YjVhNCBcdWM3NGNcdWFjYzRcdWM3NzhcdWM5YzAgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWI5YzhcdWI1MTRcdWM3NTggXHVjY2FiIFx1Yzc0Y1x1YzczY1x1Yjg1YyZuYnNwO1x1YjA5OFx1YzYyNFx1YjI5NCBcdWM5MTFcdWMyZWNcdWM3NGNcdWM3NzQgXHVhYzAwXHVjN2E1IFx1YjljZVx1Yzc0MCBcdWM3NGNcdWFjYzRcdWFjMDAmbmJzcDtcdWFkZjggXHVjNzRjXHVjNTQ1XHVjNzU4IFx1Yzc0Y1x1YWNjNFx1Yzc3NFx1YjJlNC4mbmJzcDtcdWFjMDBcdWIyZThcdWM4NzBcdWM2NDAgXHViMmU0XHVjN2E1XHVjODcwXHVjNzU4IFx1YzkxMVx1YzJlY1x1Yzc0YyBcdWFjMWNcdWMyMThcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjNzRjXHVjNzNjXHViODVjIFx1Yzc0Y1x1YWNjNFx1Yjk3YyBcdWFjYjBcdWM4MTVcdWQ1NWNcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOSBcdWM3NGNcdWM3NDAgXHVhYzAwXHViMmU4XHVjODcwXHVjNzc4IFx1YWNiZFx1YzZiMCBBLCBELCBcdWI2MTBcdWIyOTQgRVx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YjJlNFx1YzdhNVx1Yzg3MFx1Yzc3OCBcdWFjYmRcdWM2YjAgQywgRiBcdWI2MTBcdWIyOTQgR1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzcyMFx1YmE4NVx1ZDU1YyBcdWM3NGNcdWM1NDVcdWM3NzggRnImZWdyYXZlO3JlIEphY3F1ZXNcdWM3NTggXHVjNTQ1XHViY2Y0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkNEfEVDfENEfEVDfEVGfEd8RUZ8R3xHQUdGfEVDfEdBR0Z8RUN8Q0d8Q3xDR3xDPFwvcD5cclxuXHJcbjxwPnxcdWIyOTQgXHVhYzAxIFx1YjljOFx1YjUxNFx1Yjk3YyBcdWIwOThcdWIyMDRcdWIyOTQgXHViOWM4XHViNTE0XHVjMTIwXHVjNzc0XHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgXHVhYzAxIFx1YjljOFx1YjUxNFx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzc0Y1x1Yzc0NCBcdWM4MDFcdWM1YjRcdWJjZjRcdWJhNzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC4gKEMsIEUsIEMsIEUsIEUsIEcsIEUsIEcsIEcsIEUsIEcsIEUsIEMsIEMsIEMsIEMpIFx1YzVlY1x1YWUzMFx1YzExYyAoQywgQywgRywgRywgRywgRywgQywgQywgQywgQylcdWIyOTQgXHViMmU0XHVjN2E1XHVjODcwXHVjNzU4IFx1YzkxMVx1YzJlY1x1Yzc0Y1x1Yzc3NFx1YWNlMCwgKEUsIEUsIEUsIEUsIEUsIEUpXHViMjk0IFx1YWMwMFx1YjJlOFx1Yzg3MFx1Yzc1OCBcdWM5MTFcdWMyZWNcdWM3NGNcdWM3NzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjNzc0IFx1Yzc0Y1x1YzU0NVx1Yzc0MCBcdWIyZTRcdWM3YTVcdWM4NzBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc0Y1x1YzU0NVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc0Y1x1YzU0NVx1Yzc0MCB7JnF1b3Q7QSZxdW90OywgJnF1b3Q7QiZxdW90OywgJnF1b3Q7QyZxdW90OywgJnF1b3Q7RCZxdW90OywgJnF1b3Q7RSZxdW90OywgJnF1b3Q7RiZxdW90OywgJnF1b3Q7RyZxdW90OywgJnF1b3Q7fCZxdW90O31cdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhZTM4XHVjNzc0XHViMjk0IDVcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIHxcdWFjMDAgXHVjNWYwXHVjMThkXHVkNTc0XHVjMTFjIFx1YjRmMVx1YzdhNVx1ZDU1OFx1YWM3MFx1YjA5OCwmbmJzcDtcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjNTkxXHVjYWJkIFx1YjA1ZFx1YzVkMCBcdWIwOThcdWM2MjRcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWIyZTRcdWM3YTVcdWM4NzBcdWI3N2NcdWJhNzQgQy1tYWpvciwgXHVhYzAwXHViMmU4XHVjODcwXHViNzdjXHViYTc0IEEtbWlub3JcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWQ1NmRcdWMwYzEgXHViNDU4IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI4NWMgXHViMmY1XHVjNzc0IFx1YWNiMFx1YzgxNVx1YjQxOFx1YjI5NCBcdWM3ODVcdWI4MjVcdWI5Y2MgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjUyMTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMSkVTVFZJQ0EiLCJkZXNjcmlwdGlvbiI6IjxwPlZlcm9uaWNhIGF0dGVuZHMgYSBtdXNpYyBhY2FkZW15LiBTaGUgd2FzIGdpdmVuIGEgbXVzaWMgc2hlZXQgb2YgYSBjb21wb3NpdGlvbiB3aXRoIG9ubHkgbm90ZXMgKHdpdGhvdXQgYW5ub3RhdGlvbnMpLCBhbmQgbmVlZHMgdG8gcmVjb2duaXNlIHRoZSBzY2FsZSB1c2VkLiBJbiB0aGlzIHByb2JsZW0sIHdlIHdpbGwgbGltaXQgb3Vyc2VsdmVzIHRvIG9ubHkgdGhlIHR3byBtb3N0IGZyZXF1ZW50bHkgdXNlZCAoYW5kIHVzdWFsbHkgdGF1Z2h0IGluIHNjaG9vbHMgZmlyc3QpIHNjYWxlczogQS1taW5vciBhbmQgQy1tYWpvci4gVGhpcyBkb2VzbiYjMzk7dCBtYWtlIHRoZW0gc2ltcGxlciBvciBtb3JlIGJhc2ljIHRoYW4gb3RoZXIgbWlub3IgYW5kIG1ham9yIHNjYWxlcyAmbmRhc2g7IGFsbCBtaW5vciBzY2FsZXMgYXJlIG11dHVhbGx5IGVxdWl2YWxlbnQgc2F2ZSBmb3IgdHJhbnNsYXRpb24sIGFuZCBzbyBhcmUgbWFqb3Igc2NhbGVzLjxcL3A+XHJcblxyXG48cD5TdGlsbCwgb3V0IG9mIHRoZSAxMiB0b25lcyBvZiBhbiBvY3RhdmUge0EsIEEjLCBCLCBDLCBDIywgRCwgRCMsIEUsIEYsIEYjLCBHLCBHI30gdXNlZCBpbiBtb2Rlcm4gbXVzaWMsIEEtbWlub3IgYW5kIEMtbWFqb3Igc2NhbGVzIGRvIHVzZSB0aGUgdG9uZXMgd2l0aCBzaG9ydGVzdCBuYW1lczogQS1taW5vciBpcyBkZWZpbmVkIGFzIGFuIG9yZGVyZWQgc2VwdHVwbGUgKEEsIEIsIEMsIEQsIEUsIEYsIEcpLCBhbmQgQy1tYWpvciBhcyAoQywgRCwgRSwgRiwgRywgQSwgQikuIE5vdGljZSB0aGF0IHRoZSBzZXRzIG9mIHRvbmVzIG9mIHRoZXNlIHR3byBzY2FsZXMgYXJlIGVxdWFsLiBXaGF0JiMzOTtzIHRoZSBkaWZmZXJlbmNlPyBUaGUgY2F0Y2ggaXMgdGhhdCBub3Qgb25seSB0aGUgc2V0IG9mIHRvbmVzLCBidXQgYWxzbyB0aGVpciB1c2FnZSwgZGV0ZXJtaW5lcyBhIHNjYWxlLiBTcGVjaWZpY2FsbHksIHRoZSB0b25pYyAodGhlIGZpcnN0IHRvbmUgb2YgYSBzY2FsZSksIHN1YmRvbWluYW50ICh0aGUgZm91cnRoIHRvbmUpIGFuZCBkb21pbmFudCAodGhlIGZpZnRoIHRvbmUpIGFyZSB0aGUgcHJpbWFyeSBjYW5kaWRhdGVzIGZvciBhY2NlbnRlZCB0b25lcyBpbiBhIGNvbXBvc2l0aW9uLiBJbiBBLW1pbm9yLCB0aGVzZSBhcmUgQSwgRCwgYW5kIEUsIGFuZCBpbiBDLW1ham9yLCB0aGV5IGFyZSBDLCBGLCBhbmQgRy4gV2Ugd2lsbCBuYW1lIHRoZXNlIHRvbmVzIG1haW4gdG9uZXMuPFwvcD5cclxuXHJcbjxwPkFyZW4mIzM5O3QgdGhlIHNjYWxlcyBzdGlsbCBlcXVpdmFsZW50IHNhdmUgZm9yIHRyYW5zbGF0aW9uPyBUaGV5IGFyZSBub3Q6IGZvciBleGFtcGxlLCB0aGUgdGhpcmQgdG9uZSBvZiBBbWlub3IgKEMpIGlzIHRocmVlIGhhbGYtdG9uZXMgaGlnaGVyIHRoYW4gdGhlIHRvbmljIChBKSwgd2hpbGUgdGhlIHRoaXJkIHRvbmUgb2YgQy1tYWpvciAoRSkgaXMgZm91ciBoYWxmdG9uZXMgaGlnaGVyIHRoYW4gdGhlIHRvbmljIChDKS4gVGhlIGRpZmZlcmVuY2UsIHRoZXJlZm9yZSwgbGllcyBpbiB0aGUgaW50ZXJ2YWxzLiBUaGlzIG1ha2VzIG1pbm9yIHNjYWxlcyAmbGRxdW87c2FkJnJkcXVvOyBhbmQgbWFqb3Igc2NhbGVzICZsZHF1bztoYXBweSZyZHF1bzsuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0byBkZWNpZGUgaWYgYSBjb21wb3NpdGlvbiBpcyBtb3JlIGxpa2VseSB3cml0dGVuIGluIEEtbWlub3Igb3IgQy1tYWpvciBieSBjb3VudGluZyB3aGV0aGVyIHRoZXJlIGFyZSBtb3JlIG1haW4gdG9uZXMgb2YgQS1taW5vciBvciBvZiBDLW1ham9yIGFtb25nIHRoZSBhY2NlbnRlZCB0b25lcyAodGhlIGZpcnN0IHRvbmVzIGluIGVhY2ggbWVhc3VyZSkuIElmIHRoZXJlIGlzIGFuIGVxdWFsIG51bWJlciBvZiBtYWluIHRvbmVzLCBkZXRlcm1pbmUgdGhlIHNjYWxlIGJhc2VkIG9uIHRoZSBsYXN0IHRvbmUgKHdoaWNoIGlzIGd1YXJhbnRlZWQgdG8gYmUgZWl0aGVyIEEsIEQsIG9yIEUmbmJzcDtmb3IgQS1taW5vciBvciBDLCBGLCBvciBHJm5ic3A7Zm9yIEMtbWFqb3IgaW4gYW55IHN1Y2ggdGVzdCBjYXNlKS48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGV4YW1pbmUgdGhlIHdlbGwta25vd24gbWVsb2R5ICZsZHF1bztGciZlZ3JhdmU7cmUgSmFjcXVlczo8XC9wPlxyXG5cclxuPHA+Q0R8RUN8Q0R8RUN8RUZ8R3xFRnxHfEdBR0Z8RUN8R0FHRnxFQ3xDR3xDfENHfEM8XC9wPlxyXG5cclxuPHA+VGhlIGNoYXJhY3RlciAmbGRxdW87fCZyZHF1bzsgc2VwYXJhdGVzIG1lYXN1cmVzLCBzbyB0aGUgYWNjZW50ZWQgdG9uZXMgYXJlLCBpbiBvcmRlcjogQywgRSwgQywgRSwgRSwgRywgRSwgRywgRywgRSwgRywgRSwgQywgQywgQywgQy4gVGVuIG9mIHRoZW0gKEMsIEMsIEcsIEcsIEcsIEcsIEMsIEMsIEMsIEMpIGFyZSBtYWluIHRvbmVzIG9mIEMtbWFqb3IsIHdoaWxlIHNpeCAoRSwgRSwgRSwgRSwgRSwgRSkgYXJlIG1haW4gdG9uZXMgb2YgQS1taW5vci4gVGhlcmVmb3JlLCBvdXIgYmVzdCBlc3RpbWF0ZSBpcyB0aGF0IHRoZSBzb25nIHdhcyB3cml0dGVuIGluIEMtbWFqb3IuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNlcXVlbmNlIG9mIGF0IGxlYXN0IDUsIGFuZCBhdCBtb3N0IDEwMCwgY2hhcmFjdGVycyBmcm9tIHRoZSBzZXQgeyZsZHF1bztBJnJkcXVvOywgJmxkcXVvO0ImcmRxdW87LCAmbGRxdW87QyZyZHF1bzssICZsZHF1bztEJnJkcXVvOywgJmxkcXVvO0UmcmRxdW87LCAmbGRxdW87RiZyZHF1bzssICZsZHF1bztHJnJkcXVvOywgJmxkcXVvO3wmcmRxdW87fS4gVGhpcyBpcyBhIHNpbXBsaWZpZWQgbm90YXRpb24gZm9yIGEgY29tcG9zaXRpb24sIHdoZXJlIHRoZSBjaGFyYWN0ZXIgJmxkcXVvO3wmcmRxdW87IHNlcGFyYXRlcyBtZWFzdXJlcy4gVGhlIGNoYXJhY3RlcnMgJmxkcXVvO3wmcmRxdW87IHdpbGwgbmV2ZXIgYXBwZWFyIGFkamFjZW50IHRvIG9uZSBhbm90aGVyLCBhdCB0aGUgYmVnaW5uaW5nLCBvciBhdCB0aGUgZW5kIG9mIHRoZSBzZXF1ZW5jZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSB0ZXh0Jm5ic3A7JmxkcXVvO0MtbWFqb3ImcmRxdW87IChmb3IgQy1tYWpvcikgb3IgJmxkcXVvO0EtbWlub3ImcmRxdW87IChmb3IgQSBtaW5vcikuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #5 1번