시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB180251818.750%

문제

배비지등의 디지털 방식 조판이 없었던 시대에는, 조판은 숙련공들만이 할 수 있는 예술의 일종이었다. 인쇄 공간 절약과 아름다움을 위해 특정한 문자의 조합은 하나의 문자로 나타내었으며 이것을 ligature라 한다. 예를 들면 a-e의 ligature는 ‘æ’이며 f-i의 ligature는 ‘fi’이다. (힌트에 가능한 모든 ligature 조합을 표시한 표가 있다)

또한 소문자 s를 나타내는 방법에는 “long s”와 “short s” 두 가지 방법이 있었으며, 오늘날에는“short s”의 형태만 쓰인다. 어떤 방법을 쓸지 결정하는 규칙은 이상하지만 복잡하지는 않다.

  1. Short s는 단어의 끝 또는 하이픈(-)과 어퍼스트로피(`)같은 단어 속에 있는 구두점 앞에 쓴다.
    • 예) programs, ſucceſs, hocus-pocus, revis’d
  2. Short s는 ‘f’, ‘b’, ‘k’앞에 쓴다.
    • 예) transfer, husband, ask, ſucceſsful
  3. ‘ss’로 끝나는 단어 뒤에 ‘s’로 시작하는 단어가 합성되어 ‘sss’가 포함된 단어의 경우, 가운데 s는 short s로, 나머지 s는 long s로 쓴다.
    • 예) croſsſtitch, croſsſtaff
  4. 위의 경우 이외에는 모두 long s로 쓴다.

조판에 있어 “단어”라는 말이 “식별자”와는 다른 것임에 주의하자. 식별자는 ‘_’나 ‘\$’같은 구두점도 포함할 수 있는 반면, 단어는 문자만을 의미한다. 따라서 “radius3”이나 “adios_amigio”같은 식별자는 “radiu∫3”, “adio∫_amigo”가 아니라 “radius3”, “adios_amigo”로 조판된다.

입력

입력의 첫 줄에 테스트의 개수인 정수 P(1 ≤ P ≤ 1000)가 주어진다.

각각의 테스트는 1000자 이하의 문자열이 한 줄로 주어진다. 입력으로 주어지는 문자열은 알파벳 대문자, 소문자, 숫자, 공백 그리고 다음 특수문자 .,"'$;:?()-<>=!로만 이루어져 있다.

출력

각각의 테스트에 대해 입력 문자열을 적절한 ligature와 “long s” 코드로 대체하여 출력한다. 다음 페이지의 표에 기호와 ligature에 대응하는 코드가 표시되어 있다. (short s는 바꾸지 않고 그대로 출력하며, ‘IE’와 ‘OE’는 대문자 I-E, 대문자 O-E조합에 한해서 ligature로 나타낸다.)

예제 입력 1

3
Last night, we went to see
"Oedipus Rex" at the
AEgyptian's theater.

예제 출력 1

La[longst] night, we went to [longs]ee 
"[OE]dipus Rex" at the 
[AE]gyptian's theater.

힌트

입력 심볼 출력 코드
AE Æ [AE]
ae æ [ae]
OE Π[OE]
oe œ [oe]
ct [ct]
ff [ff]
fi [fi]
fl [fl]
ffi [ffi]
ffl [ffl]
s (short) s s
s (long) ſ [longs]
si [longsi]
sh [longsh]
sl [longsl]
ss [longss]
st [longst]
ssi [longssi]

long과 short s는 혼합해서 사용할 수 있다. 예를 들어, crossstitch는 cro[longs]s[longst]itch이 된다. (cro[longs]s[longs]titch는 정답이 아니다)

W3sicHJvYmxlbV9pZCI6IjI2OTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MWJcdWIwYTBcdWM1ZDBcdWIyOTQgXHVjODcwXHVkMzEwXHVjNzQ0IFx1YzViNFx1YjViYlx1YWM4YyBcdWQ1ODhcdWM3NDRcdWFlNGM/IiwiZGVzY3JpcHRpb24iOiI8cD5cdWJjMzBcdWJlNDRcdWM5YzBcdWI0ZjFcdWM3NTggXHViNTE0XHVjOWMwXHVkMTM4IFx1YmMyOVx1YzJkZCBcdWM4NzBcdWQzMTBcdWM3NzQgXHVjNWM2XHVjNWM4XHViMzU4IFx1YzJkY1x1YjMwMFx1YzVkMFx1YjI5NCwgXHVjODcwXHVkMzEwXHVjNzQwIFx1YzIxOVx1YjgyOFx1YWNmNVx1YjRlNFx1YjljY1x1Yzc3NCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM2MDhcdWMyMjBcdWM3NTggXHVjNzdjXHVjODg1XHVjNzc0XHVjNWM4XHViMmU0LiBcdWM3NzhcdWMxYzQgXHVhY2Y1XHVhYzA0IFx1YzgwOFx1YzU3ZFx1YWNmYyBcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YzBcdWM3NDQgXHVjNzA0XHVkNTc0IFx1ZDJiOVx1YzgxNVx1ZDU1YyBcdWJiMzhcdWM3OTBcdWM3NTggXHVjODcwXHVkNTY5XHVjNzQwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHVjNWM4XHVjNzNjXHViYTcwIFx1Yzc3NFx1YWM4M1x1Yzc0NCBsaWdhdHVyZVx1Yjc3YyBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQgYS1lXHVjNzU4IGxpZ2F0dXJlXHViMjk0ICZsc3F1bzsmYWVsaWc7JnJzcXVvO1x1Yzc3NFx1YmE3MCBmLWlcdWM3NTggbGlnYXR1cmVcdWIyOTQgJmxzcXVvO1x1ZmIwMSZyc3F1bztcdWM3NzRcdWIyZTQuIChcdWQ3OGNcdWQyYjhcdWM1ZDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBsaWdhdHVyZSBcdWM4NzBcdWQ1NjlcdWM3NDQgXHVkNDVjXHVjMmRjXHVkNTVjIFx1ZDQ1Y1x1YWMwMCBcdWM3ODhcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1YjYxMFx1ZDU1YyBcdWMxOGNcdWJiMzhcdWM3OTAgc1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViYzI5XHViYzk1XHVjNWQwXHViMjk0ICZsZHF1bztsb25nIHMmcmRxdW87XHVjNjQwICZsZHF1bztzaG9ydCBzJnJkcXVvOyBcdWI0NTAgXHVhYzAwXHVjOWMwIFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM3ODhcdWM1YzhcdWM3M2NcdWJhNzAsIFx1YzYyNFx1YjI5OFx1YjBhMFx1YzVkMFx1YjI5NCZsZHF1bztzaG9ydCBzJnJkcXVvO1x1Yzc1OCBcdWQ2MTVcdWQwZGNcdWI5Y2MgXHVjNGYwXHVjNzc4XHViMmU0LiBcdWM1YjRcdWI1YTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1YzRmOFx1YzljMCBcdWFjYjBcdWM4MTVcdWQ1NThcdWIyOTQgXHVhZGRjXHVjZTU5XHVjNzQwIFx1Yzc3NFx1YzBjMVx1ZDU1OFx1YzljMFx1YjljYyBcdWJjZjVcdWM3YTFcdWQ1NThcdWM5YzBcdWIyOTQgXHVjNTRhXHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlNob3J0IHNcdWIyOTQgXHViMmU4XHVjNWI0XHVjNzU4IFx1YjA1ZCBcdWI2MTBcdWIyOTQgXHVkNTU4XHVjNzc0XHVkNTA4KC0pXHVhY2ZjIFx1YzViNFx1ZDM3Y1x1YzJhNFx1ZDJiOFx1Yjg1Y1x1ZDUzYyhgKVx1YWMxOVx1Yzc0MCBcdWIyZThcdWM1YjQgXHVjMThkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFkNmNcdWI0NTBcdWM4MTAgXHVjNTVlXHVjNWQwIFx1YzRmNFx1YjJlNC5cclxuXHQ8dWw+XHJcblx0XHQ8bGk+XHVjNjA4KSZuYnNwO3Byb2dyYW1zLCBcdTAxN2Z1Y2NlXHUwMTdmcywgaG9jdXMtcG9jdXMsIHJldmlzJnJzcXVvO2Q8XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuXHQ8bGk+U2hvcnQgc1x1YjI5NCAmbHNxdW87ZiZyc3F1bzssICZsc3F1bztiJnJzcXVvOywgJmxzcXVvO2smcnNxdW87XHVjNTVlXHVjNWQwIFx1YzRmNFx1YjJlNC5cclxuXHQ8dWw+XHJcblx0XHQ8bGk+XHVjNjA4KSZuYnNwO3RyYW5zZmVyLCBodXNiYW5kLCBhc2ssIFx1MDE3ZnVjY2VcdTAxN2ZzZnVsPFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcblx0PGxpPiZsc3F1bztzcyZyc3F1bztcdWI4NWMgXHViMDVkXHViMDk4XHViMjk0IFx1YjJlOFx1YzViNCBcdWI0YTRcdWM1ZDAgJmxzcXVvO3MmcnNxdW87XHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWIyZThcdWM1YjRcdWFjMDAgXHVkNTY5XHVjMTMxXHViNDE4XHVjNWI0ICZsc3F1bztzc3MmcnNxdW87XHVhYzAwIFx1ZDNlY1x1ZDU2OFx1YjQxYyBcdWIyZThcdWM1YjRcdWM3NTggXHVhY2JkXHVjNmIwLCBcdWFjMDBcdWM2YjRcdWIzNzAgc1x1YjI5NCBzaG9ydCBzXHViODVjLCBcdWIwOThcdWJhMzhcdWM5YzAgc1x1YjI5NCBsb25nIHNcdWI4NWMgXHVjNGY0XHViMmU0LlxyXG5cdDx1bD5cclxuXHRcdDxsaT5cdWM2MDgpIGNyb1x1MDE3ZnNcdWZiMDVpdGNoLCBjcm9cdTAxN2ZzXHVmYjA1YVx1ZmIwMDxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG5cdDxsaT5cdWM3MDRcdWM3NTggXHVhY2JkXHVjNmIwIFx1Yzc3NFx1YzY3OFx1YzVkMFx1YjI5NCBcdWJhYThcdWI0NTAgbG9uZyBzXHViODVjIFx1YzRmNFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM4NzBcdWQzMTBcdWM1ZDAgXHVjNzg4XHVjNWI0ICZsZHF1bztcdWIyZThcdWM1YjQmcmRxdW87XHViNzdjXHViMjk0IFx1YjlkMFx1Yzc3NCAmbGRxdW87XHVjMmRkXHViY2M0XHVjNzkwJnJkcXVvO1x1YzY0MFx1YjI5NCBcdWIyZTRcdWI5NzggXHVhYzgzXHVjNzg0XHVjNWQwIFx1YzhmY1x1Yzc1OFx1ZDU1OFx1Yzc5MC4gXHVjMmRkXHViY2M0XHVjNzkwXHViMjk0ICZsc3F1bztfJnJzcXVvO1x1YjA5OCAmbHNxdW87XFwkJnJzcXVvO1x1YWMxOVx1Yzc0MCBcdWFkNmNcdWI0NTBcdWM4MTBcdWIzYzQgXHVkM2VjXHVkNTY4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzE4XHViYTc0LCBcdWIyZThcdWM1YjRcdWIyOTQgXHViYjM4XHVjNzkwXHViOWNjXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjICZsZHF1bztyYWRpdXMzJnJkcXVvO1x1Yzc3NFx1YjA5OCAmbGRxdW87YWRpb3NfYW1pZ2lvJnJkcXVvO1x1YWMxOVx1Yzc0MCBcdWMyZGRcdWJjYzRcdWM3OTBcdWIyOTQgJmxkcXVvO3JhZGl1JmludDszJnJkcXVvOywgJmxkcXVvO2FkaW8maW50O19hbWlnbyZyZHF1bztcdWFjMDAgXHVjNTQ0XHViMmM4XHViNzdjICZsZHF1bztyYWRpdXMzJnJkcXVvOywgJmxkcXVvO2FkaW9zX2FtaWdvJnJkcXVvO1x1Yjg1YyBcdWM4NzBcdWQzMTBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjhcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc4IFx1YzgxNVx1YzIxOCBQKDEgJmxlOyBQICZsZTsgMTAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4XHViMjk0IDEwMDBcdWM3OTAgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MCwgXHVjMThjXHViYjM4XHVjNzkwLCBcdWMyMmJcdWM3OTAsIFx1YWNmNVx1YmMzMSZuYnNwO1x1YWRmOFx1YjlhY1x1YWNlMCBcdWIyZTRcdWM3NGMgXHVkMmI5XHVjMjE4XHViYjM4XHVjNzkwIDxjb2RlPi4sJnF1b3Q7JiMzOTskOzo/KCktJmx0OyZndDs9ITxcL2NvZGU+XHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjNzg1XHViODI1IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWM4MDFcdWM4MDhcdWQ1NWMgbGlnYXR1cmVcdWM2NDAgJmxkcXVvO2xvbmcgcyZyZHF1bzsgXHVjZjU0XHViNGRjXHViODVjIFx1YjMwMFx1Y2NiNFx1ZDU1OFx1YzVlYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWQzOThcdWM3NzRcdWM5YzBcdWM3NTggXHVkNDVjXHVjNWQwIFx1YWUzMFx1ZDYzOFx1YzY0MCBsaWdhdHVyZVx1YzVkMCBcdWIzMDBcdWM3NTFcdWQ1NThcdWIyOTQgXHVjZjU0XHViNGRjXHVhYzAwIFx1ZDQ1Y1x1YzJkY1x1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIChzaG9ydCBzXHViMjk0IFx1YmMxNFx1YWZiOFx1YzljMCBcdWM1NGFcdWFjZTAgXHVhZGY4XHViMzAwXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3MCwgJmxzcXVvO0lFJnJzcXVvO1x1YzY0MCAmbHNxdW87T0UmcnNxdW87XHViMjk0IFx1YjMwMFx1YmIzOFx1Yzc5MCBJLUUsIFx1YjMwMFx1YmIzOFx1Yzc5MCBPLUVcdWM4NzBcdWQ1NjlcdWM1ZDAgXHVkNTVjXHVkNTc0XHVjMTFjIGxpZ2F0dXJlXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4pPFwvcD5cclxuIiwiaGludCI6Ijx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDoyNSVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjEwJVwiPlx1Yzc4NVx1YjgyNTxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo1JVwiPlx1YzJlY1x1YmNmYzxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDoxMCVcIj5cdWNkOWNcdWI4MjUgXHVjZjU0XHViNGRjPFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5BRTxcL3RkPlxyXG5cdFx0XHQ8dGQ+JkFFbGlnOzxcL3RkPlxyXG5cdFx0XHQ8dGQ+W0FFXTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5hZTxcL3RkPlxyXG5cdFx0XHQ8dGQ+JmFlbGlnOzxcL3RkPlxyXG5cdFx0XHQ8dGQ+W2FlXTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5PRTxcL3RkPlxyXG5cdFx0XHQ8dGQ+Jk9FbGlnOzxcL3RkPlxyXG5cdFx0XHQ8dGQ+W09FXTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5vZTxcL3RkPlxyXG5cdFx0XHQ8dGQ+Jm9lbGlnOzxcL3RkPlxyXG5cdFx0XHQ8dGQ+W29lXTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5jdDxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHVlMDA0PFwvdGQ+XHJcblx0XHRcdDx0ZD5bY3RdPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPmZmPFwvdGQ+XHJcblx0XHRcdDx0ZD5cdWZiMDA8XC90ZD5cclxuXHRcdFx0PHRkPltmZl08XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+Zmk8XC90ZD5cclxuXHRcdFx0PHRkPlx1ZmIwMTxcL3RkPlxyXG5cdFx0XHQ8dGQ+W2ZpXTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5mbDxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHVmYjAyPFwvdGQ+XHJcblx0XHRcdDx0ZD5bZmxdPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPmZmaTxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHVmYjAzPFwvdGQ+XHJcblx0XHRcdDx0ZD5bZmZpXTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5mZmw8XC90ZD5cclxuXHRcdFx0PHRkPlx1ZmIwNDxcL3RkPlxyXG5cdFx0XHQ8dGQ+W2ZmbF08XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+cyAoc2hvcnQpPFwvdGQ+XHJcblx0XHRcdDx0ZD5zPFwvdGQ+XHJcblx0XHRcdDx0ZD5zPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPnMgKGxvbmcpPFwvdGQ+XHJcblx0XHRcdDx0ZD5cdTAxN2Y8XC90ZD5cclxuXHRcdFx0PHRkPltsb25nc108XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+c2k8XC90ZD5cclxuXHRcdFx0PHRkPlx1ZTAwYTxcL3RkPlxyXG5cdFx0XHQ8dGQ+W2xvbmdzaV08XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+c2g8XC90ZD5cclxuXHRcdFx0PHRkPlx1ZTAwODxcL3RkPlxyXG5cdFx0XHQ8dGQ+W2xvbmdzaF08XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+c2w8XC90ZD5cclxuXHRcdFx0PHRkPlx1ZTAwYjxcL3RkPlxyXG5cdFx0XHQ8dGQ+W2xvbmdzbF08XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+c3M8XC90ZD5cclxuXHRcdFx0PHRkPlx1ZTAwOTxcL3RkPlxyXG5cdFx0XHQ8dGQ+W2xvbmdzc108XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+c3Q8XC90ZD5cclxuXHRcdFx0PHRkPlx1ZmIwNTxcL3RkPlxyXG5cdFx0XHQ8dGQ+W2xvbmdzdF08XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+c3NpPFwvdGQ+XHJcblx0XHRcdDx0ZD5cdWUwMDY8XC90ZD5cclxuXHRcdFx0PHRkPltsb25nc3NpXTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+bG9uZ1x1YWNmYyBzaG9ydCBzXHViMjk0IFx1ZDYzY1x1ZDU2OVx1ZDU3NFx1YzExYyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgY3Jvc3NzdGl0Y2hcdWIyOTQgY3JvW2xvbmdzXXNbbG9uZ3N0XWl0Y2hcdWM3NzQgXHViNDFjXHViMmU0LiAoY3JvW2xvbmdzXXNbbG9uZ3NddGl0Y2hcdWIyOTQgXHVjODE1XHViMmY1XHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNCk8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI2OTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJPbGQgRmFmaGlvbmVkIFR5cGVcdTAxN2ZldHRpbmciLCJkZXNjcmlwdGlvbiI6IjxwPm4gT2xkZW4gRGF5cywgYmVmb3JlIGRpZ2l0YWwgdHlwZXNldHRpbmcgKGJlZm9yZSBCYWJiYWdlLCBldmVuKSwgdHlwZXNldHRpbmcgd2FzIGFuIGFydCwgcHJhY3RpY2VkIGJ5IGhpZ2hseSBza2lsbGVkIGNyYWZ0c21lbi4gQ2VydGFpbiBjaGFyYWN0ZXIgY29tYmluYXRpb25zLCBzdWNoIGFzIGEtZSBvciBmLWkgd2VyZSB0eXBlc2V0IGFzIGEgc2luZ2xlIGNoYXJhY3RlciwgY2FsbGVkIGEgbGlnYXR1cmUsIHRvIHNhdmUgc3BhY2UgYW5kIHRvIG1ha2UgdGhlIGNoYXJhY3RlcnMgbG9vayBiZXR0ZXIgdG9nZXRoZXIgb24gdGhlIHByaW50ZWQgcGFnZSAodGhlIGxpZ2F0dXJlcyBmb3IgYS1lIGFuZCBmLWkgd2VyZSAmbHNxdW87JmFlbGlnOyZyc3F1bzsgYW5kICZsc3F1bztcdWZiMDEmcnNxdW87LCByZXNwZWN0aXZlbHk7IHRoZSB0YWJsZSBvbiB0aGUgbmV4dCBwYWdlLCBsaXN0cyBhbGwgcG9zc2libGUgbGlnYXR1cmUgY29tYmluYXRpb25zKS48XC9wPlxyXG5cclxuPHA+SW4gYWRkaXRpb24sIHRoZXJlIHdlcmUgdHdvIGRpZmZlcmVudCB2ZXJzaW9ucyBvZiB0aGUgbG93ZXJjYXNlIGxldHRlciBzOiB0aGUgJmxkcXVvO2xvbmcgcyZyZHF1bzsgYW5kIHRoZSAmbGRxdW87c2hvcnQgcyZyZHF1bzsuIE9ubHkgdGhlIHNob3J0IHMgaXMgdXNlZCB0b2RheS4gVGhlIHJ1bGVzIGZvciB3aGVuIHRvIHVzZSB3aGljaCB2ZXJzaW9uIGFyZSBvZGQsIGJ1dCBzdHJhaWdodGZvcndhcmQ6PFwvcD5cclxuXHJcbjxwPlNob3J0IHMgaXMgdXNlZCBhdCB0aGUgZW5kIG9mIGEgd29yZCwgb3IgYmVmb3JlIHB1bmN0dWF0aW9uIHdpdGhpbiBhIHdvcmQsIHN1Y2ggYXMgYSBoeXBoZW4gb3IgYXBvc3Ryb3BoZTogcHJvZ3JhbXMsIHN1Y2Nlc3MsIGhvY3VzLXBvY3VzLCByZXZpcyZyc3F1bztkLiAocHJvZ3JhbXMsIFx1MDE3ZnVjY2VcdTAxN2ZzLCBob2N1cy1wb2N1cywgcmV2aXMmcnNxdW87ZCk8YnIgXC8+XHJcblNob3J0IHMgaXMgdXNlZCBiZWZvcmUgdGhlIGxldHRlcnMgJmxzcXVvO2YmcnNxdW87LCAmbHNxdW87YiZyc3F1bzssIG9yICZsc3F1bztrJnJzcXVvOzogdHJhbnNmZXIsIGh1c2JhbmQsIGFzaywgc3VjY2Vzc2Z1bC4gKHRyYW5zZmVyLCBodXNiYW5kLCBhc2ssIFx1MDE3ZnVjY2VcdTAxN2ZzZnVsKTxiciBcLz5cclxuTG9uZyBzIGlzIHVzZWQgZXZlcnl3aGVyZSBlbHNlLCBleGNlcHQuLi48YnIgXC8+XHJcbkl0IGlzIHBvc3NpYmxlIHRoYXQgYSBjb21wb3VuZCB3b3JkIGNvbnNpc3RzIG9mIGEgd29yZCBlbmRpbmcgaW4gYSBkb3VibGUgcyBmb2xsb3dlZCBieSBhIHdvcmQgYmVnaW5uaW5nIHdpdGggcyAodGhpcyBpcyB0aGUgb25seSBzaXR1YXRpb24gd2hlcmUgdGhlIHNlcXVlbmNlICZsZHF1bztzc3MmcmRxdW87IG9jY3VycyBpbiBFbmdsaXNoIHRleHQpLiBJbiB0aGlzIGNhc2UsIHRoZSBtaWRkbGUgcyBpcyBzZXQgc2hvcnQgYW5kIHRoZSBvdGhlciB0d28gYXJlIHNldCBsb25nOiBjcm9zc3N0aXRjaCwgY3Jvc3NzdGFmZi4gKGNyb1x1MDE3ZnNcdWZiMDVpdGNoLCBjcm9cdTAxN2ZzXHVmYjA1YVx1ZmIwMCk8XC9wPlxyXG5cclxuPHA+Tm90ZSB0aGF0IGEgJmxkcXVvO3dvcmQmcmRxdW87IGlzIG5vdCB0aGUgc2FtZSB0aGluZyBhcyBhbiAmbGRxdW87aWRlbnRpZmllci4mcmRxdW87IFdoaWxlIGlkZW50aWZpZXJzIGNhbiBjb250YWluIHB1bmN0dWF0aW9uIG1hcmtzIHN1Y2ggYXMgJmxzcXVvO18mcnNxdW87IG9yICZsc3F1bztcXCQmcnNxdW87LCB3b3JkcyBjYW4gY29udGFpbiBvbmx5IGxldHRlcnMgKGF0IGxlYXN0IGFzIGZhciBhcyB0eXBvZ3JhcGhlcnMgYXJlIGNvbmNlcm5lZCkuIFRoZXJlZm9yZSwgaWRlbnRpZmllcnMgbGlrZSAmbGRxdW87cmFkaXVzMyZyZHF1bzsgYW5kICZsZHF1bzthZGlvc19hbWlnbyZyZHF1bzsgd291bGQgYmUgdHlwZXNldCBhcyAmbGRxdW87cmFkaXVzMyZyZHF1bzsgYW5kICZsZHF1bzthZGlvc19hbWlnbywmcmRxdW87IHJlc3BlY3RpdmVseSwgcmF0aGVyIHRoYW4gJmxkcXVvO3JhZGl1XHUwMTdmMyZyZHF1bzsgYW5kICZsZHF1bzthZGlvXHUwMTdmX2FtaWdvLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBQLCAoMSAmbGU7IFAgJmxlOyAxMDAwKSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdGhhdCBmb2xsb3cuIEVhY2ggZGF0YSBzZXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHRoZSBkYXRhIHNldCBudW1iZXIsIGZvbGxvd2VkIGJ5IGEgc3BhY2UsIGZvbGxvd2VkIGJ5IGEgc3RyaW5nIG9mIG5vIG1vcmUgdGhhbiAxMDAwIGNoYXJhY3RlcnMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQsIHByaW50IHRoZSBkYXRhIHNldCBudW1iZXIsIGEgc3BhY2UsIGFuZCB0aGUgaW5wdXQgc3RyaW5nLCB3aXRoIHRoZSBhcHByb3ByaWF0ZSBsaWdhdHVyZSBhbmQgJmxkcXVvO2xvbmcgcyZyZHF1bzsgY29kZXMgc3Vic3RpdHV0ZWQgaW50byB0aGUgc3RyaW5nLiBUaGUgdGFibGUgb24gdGhlIG5leHQgcGFnZSBzaG93cyB0aGUgY29kZSBzdHJpbmdzIHRvIHVzZSBmb3IgZWFjaCBzeW1ib2wgb3IgbGlnYXR1cmUgKG5vdGUgdGhhdCB0aGUgc2hvcnQgcyByZW1haW5zIHVuY2hhbmdlZCBvbiBvdXRwdXQ7IG5vdGUgYWxzbyB0aGF0ICZsc3F1bzsmQUVsaWc7JnJzcXVvOyBhbmQgJmxzcXVvOyZPRWxpZzsmcnNxdW87IGFyZSB0aGUgb25seSB1cHBlcmNhc2UgbGlnYXR1cmVzKTxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3N5bWJvbC5wbmdcIiBzdHlsZT1cImhlaWdodDo1NThweDsgd2lkdGg6NDA1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+Tm90ZSB0aGF0IHRoZSBydWxlcyBmb3IgdGhlIHVzZSBvZiBsb25nIGFuZCBzaG9ydCBzIGNhbiBjb21iaW5lIHdpdGggdGhlc2UgbGlnYXR1cmVzIGluIGludGVyZXN0aW5nIChhbmQgbm90IGFsd2F5cyBvYnZpb3VzKSB3YXlzLiBGb3IgZXhhbXBsZSwgdGhlIGlucHV0IHdvcmQgJmxkcXVvO2Nyb3Nzc3RpdGNoJnJkcXVvOyBiZWNvbWVzICZsZHF1bztjcm9bbG9uZ3Ndc1tsb25nc3RdaXRjaCwmcmRxdW87IG5vdCAmbGRxdW87Y3JvW2xvbmdzXXNbbG9uZ3NddGl0Y2gsJnJkcXVvOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > North America > Greater New York Region > 2010 Greater New York Programming Contest G번