시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 250 20 15 10.000%

문제

DNA 수열은 A, C, G, T로 이루어져 있다. DNA 수열의 GC-비율은 C와 G의 개수를 수열의 길이로 나눈 값이다. GC-비율이 높은 구간은 유전자의 시작 구간이 될 확률이 높다. 따라서, GC-비율은 매우 중요하다.

매우 긴 DNA 수열에서 수열의 모든 부분 수열 중에서 GC-비율이 가장 큰 부분 수열을 찾는 연구가 활발히 진행중이다. GC-비율이 높은 짧은 부분 수열은 의미없는 경우가 많기 때문에, 길이의 하한(lower bound)을 정해두고 부분 수열을 찾는다.

DNA 수열에서 모든 A와 T를 0으로, C와 G를 1로 바꿔서 길이가 같은 이진수열을 만들 수 있다. 이렇게 만든 이진수열의 평균값은 DNA 수열의 GC-비율과 같아진다.

인덱스 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
수열 0 0 1 0 1 0 1 1 0 1 1 0 1 1 0 1 0

이진수열이 위와 같이 주어을 때, 길이의 하한이 7이라면 평균이 최대인 부분 수열은 [7,14]가 되고, 평균은 6/8이다. 하한이 5인 경우, 평균이 최대인 부분 수열은 [7,11]이 되고, 평균은 4/5가 된다.

이진수열과 길이의 하한 L이 주어졌을 때, 길이가 적어도 L인 모든 부분 수열 중에서 평균이 최대인 부분 수열을 찾는 프로그램을 작성하시오. 같은 평균을 가지는 부분 수열이 여러 개인 경우, 길이가 짧은 것을 찾으면 된다. 길이가 짧은 것이 여러 개인 경우에는, 시작 위치가 앞서는 것을 찾는다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 이진수열의 길이 n(1 ≤ n ≤ 100,000)과 길이의 하한 L(1 ≤ L ≤ 1,000)이 주어진다. 다음 줄에는 길이가 n인 이진수열이 주어진다.

출력

각 테스트 케이스 마다 부분 수열의 시작 위치와 끝 위치를 출력한다. 

예제 입력 1

2
17 5
00101011011011010
20 4
11100111100111110000

예제 출력 1

7 11
6 9
W3sicHJvYmxlbV9pZCI6Ijg5MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJHQy1cdWJlNDRcdWM3MjgiLCJkZXNjcmlwdGlvbiI6IjxwPkROQSBcdWMyMThcdWM1ZjRcdWM3NDAgQSwgQywgRywgVFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBETkEgXHVjMjE4XHVjNWY0XHVjNzU4IEdDLVx1YmU0NFx1YzcyOFx1Yzc0MCBDXHVjNjQwIEdcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI4NWMgXHViMDk4XHViMjA4IFx1YWMxMlx1Yzc3NFx1YjJlNC4gR0MtXHViZTQ0XHVjNzI4XHVjNzc0IFx1YjE5Mlx1Yzc0MCBcdWFkNmNcdWFjMDRcdWM3NDAgXHVjNzIwXHVjODA0XHVjNzkwXHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWFkNmNcdWFjMDRcdWM3NzQgXHViNDIwIFx1ZDY1NVx1Yjk2MFx1Yzc3NCBcdWIxOTJcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgR0MtXHViZTQ0XHVjNzI4XHVjNzQwIFx1YjllNFx1YzZiMCBcdWM5MTFcdWM2OTRcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjllNFx1YzZiMCBcdWFlMzQgRE5BIFx1YzIxOFx1YzVmNFx1YzVkMFx1YzExYyBcdWMyMThcdWM1ZjRcdWM3NTggXHViYWE4XHViNGUwIFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjQgXHVjOTExXHVjNWQwXHVjMTFjIEdDLVx1YmU0NFx1YzcyOFx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjYzNlXHViMjk0IFx1YzVmMFx1YWQ2Y1x1YWMwMCBcdWQ2NWNcdWJjMWNcdWQ3ODggXHVjOWM0XHVkNTg5XHVjOTExXHVjNzc0XHViMmU0LiBHQy1cdWJlNDRcdWM3MjhcdWM3NzQgXHViMTkyXHVjNzQwIFx1YzllN1x1Yzc0MCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzQwIFx1Yzc1OFx1YmJmOFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHViOWNlXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDU1OFx1ZDU1Yyhsb3dlciBib3VuZClcdWM3NDQgXHVjODE1XHVkNTc0XHViNDUwXHVhY2UwIFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjYzNlXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5ETkEgXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjIFx1YmFhOFx1YjRlMCBBXHVjNjQwIFRcdWI5N2MgMFx1YzczY1x1Yjg1YywgQ1x1YzY0MCBHXHViOTdjIDFcdWI4NWMgXHViYzE0XHVhZmQ0XHVjMTFjIFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFjMTlcdWM3NDAgXHVjNzc0XHVjOWM0XHVjMjE4XHVjNWY0XHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHViOWNjXHViNGUwIFx1Yzc3NFx1YzljNFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWQzYzlcdWFkZTBcdWFjMTJcdWM3NDAgRE5BIFx1YzIxOFx1YzVmNFx1Yzc1OCBHQy1cdWJlNDRcdWM3MjhcdWFjZmMgXHVhYzE5XHVjNTQ0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6NTAlXCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+XHVjNzc4XHViMzcxXHVjMmE0PFwvdGg+XHJcblx0XHRcdDx0aD4xPFwvdGg+XHJcblx0XHRcdDx0aD4yPFwvdGg+XHJcblx0XHRcdDx0aD4zPFwvdGg+XHJcblx0XHRcdDx0aD40PFwvdGg+XHJcblx0XHRcdDx0aD41PFwvdGg+XHJcblx0XHRcdDx0aD42PFwvdGg+XHJcblx0XHRcdDx0aD43PFwvdGg+XHJcblx0XHRcdDx0aD44PFwvdGg+XHJcblx0XHRcdDx0aD45PFwvdGg+XHJcblx0XHRcdDx0aD4xMDxcL3RoPlxyXG5cdFx0XHQ8dGg+MTE8XC90aD5cclxuXHRcdFx0PHRoPjEyPFwvdGg+XHJcblx0XHRcdDx0aD4xMzxcL3RoPlxyXG5cdFx0XHQ8dGg+MTQ8XC90aD5cclxuXHRcdFx0PHRoPjE1PFwvdGg+XHJcblx0XHRcdDx0aD4xNjxcL3RoPlxyXG5cdFx0XHQ8dGg+MTc8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPlx1YzIxOFx1YzVmNDxcL3RoPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+XHVjNzc0XHVjOWM0XHVjMjE4XHVjNWY0XHVjNzc0IFx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjNzQ0IFx1YjU0YywgXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDU1OFx1ZDU1Y1x1Yzc3NCA3XHVjNzc0XHViNzdjXHViYTc0IFx1ZDNjOVx1YWRlMFx1Yzc3NCBcdWNkNWNcdWIzMDBcdWM3NzggXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc0MCBbNywxNF1cdWFjMDAgXHViNDE4XHVhY2UwLCBcdWQzYzlcdWFkZTBcdWM3NDAgNlwvOFx1Yzc3NFx1YjJlNC4gXHVkNTU4XHVkNTVjXHVjNzc0IDVcdWM3NzggXHVhY2JkXHVjNmIwLCBcdWQzYzlcdWFkZTBcdWM3NzQgXHVjZDVjXHViMzAwXHVjNzc4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NDAgWzcsMTFdXHVjNzc0IFx1YjQxOFx1YWNlMCwgXHVkM2M5XHVhZGUwXHVjNzQwIDRcLzVcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM5YzRcdWMyMThcdWM1ZjRcdWFjZmMgXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDU1OFx1ZDU1YyBMXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM4MDFcdWM1YjRcdWIzYzQgTFx1Yzc3OCBcdWJhYThcdWI0ZTAgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVkM2M5XHVhZGUwXHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1Yzc3OCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFjMTlcdWM3NDAgXHVkM2M5XHVhZGUwXHVjNzQ0IFx1YWMwMFx1YzljMFx1YjI5NCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NzggXHVhY2JkXHVjNmIwLCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVjOWU3XHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWNjM2VcdWM3M2NcdWJhNzQgXHViNDFjXHViMmU0LiBcdWFlMzhcdWM3NzRcdWFjMDAgXHVjOWU3XHVjNzQwIFx1YWM4M1x1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCwgXHVjMmRjXHVjNzkxIFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM1NWVcdWMxMWNcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Y2MzZVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzc0XHVjOWM0XHVjMjE4XHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NCBuKDEgJmxlOyBuICZsZTsgMTAwLDAwMClcdWFjZmMgXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDU1OFx1ZDU1YyBMKDEgJmxlOyBMICZsZTsgMSwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgblx1Yzc3OCBcdWM3NzRcdWM5YzRcdWMyMThcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWM3MDRcdWNlNThcdWM2NDAgXHViMDVkIFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiODkyNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkF2ZXJhZ2UiLCJkZXNjcmlwdGlvbiI6IjxwPkEgRE5BIHNlcXVlbmNlIGNvbnNpc3RzIG9mIGZvdXIgbGV0dGVycywgQSwgQywgRywgYW5kIFQuIFRoZSBHQy1yYXRpbyBvZiBhIEROQSBzZXF1ZW5jZSBpcyB0aGUgbnVtYmVyIG9mIENzIGFuZCBHcyBvZiB0aGUgc2VxdWVuY2UgZGl2aWRlZCBieSB0aGUgbGVuZ3RoIG9mIHRoZSBzZXF1ZW5jZS4gR0MtcmF0aW8gaXMgaW1wb3J0YW50IGluIGdlbmUgZmluZGluZyBiZWNhdXNlIEROQSBzZXF1ZW5jZXMgd2l0aCByZWxhdGl2ZWx5IGhpZ2ggR0MtcmF0aW9zIG1pZ2h0IGJlIGdvb2QgY2FuZGlkYXRlcyBmb3IgdGhlIHN0YXJ0aW5nIHBhcnRzIG9mIGdlbmVzLiBHaXZlbiBhIHZlcnkgbG9uZyBETkEgc2VxdWVuY2UsIHJlc2VhcmNoZXJzIGFyZSB1c3VhbGx5IGludGVyZXN0ZWQgaW4gbG9jYXRpbmcgYSBzdWJzZXF1ZW5jZSB3aG9zZSBHQy1yYXRpbyBpcyBtYXhpbXVtIG92ZXIgYWxsIHN1YnNlcXVlbmNlcyBvZiB0aGUgc2VxdWVuY2UuIFNpbmNlIHNob3J0IHN1YnNlcXVlbmNlcyB3aXRoIGhpZ2ggR0MtcmF0aW9zIGFyZSBzb21ldGltZXMgbWVhbmluZ2xlc3MgaW4gZ2VuZSBmaW5kaW5nLCBhIGxlbmd0aCBsb3dlciBib3VuZCBpcyBnaXZlbiB0byBlbnN1cmUgdGhhdCBhIGxvbmcgc3Vic2VxdWVuY2Ugd2l0aCBoaWdoIEdDLXJhdGlvIGNvdWxkIGJlIGZvdW5kLiBJZiwgaW4gYSBETkEgc2VxdWVuY2UsIGEgMCBpcyBhc3NpZ25lZCB0byBldmVyeSBBIGFuZCBUIGFuZCBhIDEgdG8gZXZlcnkgQyBhbmQgRywgdGhlIEROQSBzZXF1ZW5jZSBpcyB0cmFuc2Zvcm1lZCBpbnRvIGEgYmluYXJ5IHNlcXVlbmNlIG9mIHRoZSBzYW1lIGxlbmd0aC4gR0MtcmF0aW9zIGluIHRoZSBETkEgc2VxdWVuY2UgYXJlIG5vdyBlcXVpdmFsZW50IHRvIGF2ZXJhZ2VzIGluIHRoZSBiaW5hcnkgc2VxdWVuY2UuJm5ic3A7PFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDo1MCVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5Qb3NpdGlvbiBJbmRleDxcL3RoPlxyXG5cdFx0XHQ8dGg+MTxcL3RoPlxyXG5cdFx0XHQ8dGg+MjxcL3RoPlxyXG5cdFx0XHQ8dGg+MzxcL3RoPlxyXG5cdFx0XHQ8dGg+NDxcL3RoPlxyXG5cdFx0XHQ8dGg+NTxcL3RoPlxyXG5cdFx0XHQ8dGg+NjxcL3RoPlxyXG5cdFx0XHQ8dGg+NzxcL3RoPlxyXG5cdFx0XHQ8dGg+ODxcL3RoPlxyXG5cdFx0XHQ8dGg+OTxcL3RoPlxyXG5cdFx0XHQ8dGg+MTA8XC90aD5cclxuXHRcdFx0PHRoPjExPFwvdGg+XHJcblx0XHRcdDx0aD4xMjxcL3RoPlxyXG5cdFx0XHQ8dGg+MTM8XC90aD5cclxuXHRcdFx0PHRoPjE0PFwvdGg+XHJcblx0XHRcdDx0aD4xNTxcL3RoPlxyXG5cdFx0XHQ8dGg+MTY8XC90aD5cclxuXHRcdFx0PHRoPjE3PFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5TZXF1ZW5jZTxcL3RoPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+Rm9yIHRoZSBiaW5hcnkgc2VxdWVuY2UgYWJvdmUsIGlmIHRoZSBsZW5ndGggbG93ZXIgYm91bmQgaXMgNywgdGhlIG1heGltdW0gYXZlcmFnZSBpcyA2XC84IHdoaWNoIGhhcHBlbnMgaW4gdGhlIHN1YnNlcXVlbmNlIFs3LDE0XS4gSXRzIGxlbmd0aCBpcyA4LCB3aGljaCBpcyBncmVhdGVyIHRoYW4gdGhlIGxlbmd0aCBsb3dlciBib3VuZCA3LiBJZiB0aGUgbGVuZ3RoIGxvd2VyIGJvdW5kIGlzIDUsIHRoZW4gdGhlIHN1YnNlcXVlbmNlIFs3LDExXSBnaXZlcyB0aGUgbWF4aW11bSBhdmVyYWdlIDRcLzUuIFRoZSBsZW5ndGggaXMgNSB3aGljaCBpcyBlcXVhbCB0byB0aGUgbGVuZ3RoIGxvd2VyIGJvdW5kLiBGb3IgdGhlIHN1YnNlcXVlbmNlIFs3LDExXSwgNyBpcyBpdHMgc3RhcnRpbmcgaW5kZXggYW5kIDExIGlzIGl0cyBlbmRpbmcgaW5kZXguJm5ic3A7PGJyIFwvPlxyXG4mbmJzcDs8YnIgXC8+XHJcbkdpdmVuIGEgYmluYXJ5IHNlcXVlbmNlIGFuZCBhIGxlbmd0aCBsb3dlciBib3VuZCBMLCB3cml0ZSBhIHByb2dyYW0gdG8gZmluZCBhIHN1YnNlcXVlbmNlIG9mIHRoZSBiaW5hcnkgc2VxdWVuY2Ugd2hvc2UgbGVuZ3RoIGlzIGF0IGxlYXN0IEwgYW5kIHdob3NlIGF2ZXJhZ2UgaXMgbWF4aW11bSBvdmVyIGFsbCBzdWJzZXF1ZW5jZXMgb2YgdGhlIGJpbmFyeSBzZXF1ZW5jZS4gSWYgdHdvIG9yIG1vcmUgc3Vic2VxdWVuY2VzIGhhdmUgdGhlIG1heGltdW0gYXZlcmFnZSwgdGhlbiBmaW5kIHRoZSBzaG9ydGVzdCBvbmU7IGFuZCBpZiB0d28gb3IgbW9yZSBzaG9ydGVzdCBzdWJzZXF1ZW5jZXMgd2l0aCB0aGUgbWF4aW11bSBhdmVyYWdlIGV4aXN0LCB0aGVuIGZpbmQgdGhlIG9uZSB3aXRoIHRoZSBzbWFsbGVzdCBzdGFydGluZyBpbmRleC4mbmJzcDs8XC9wPiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlcnMgbiAoMSZsZTtuJmxlOzEwMCwwMDApIGFuZCBMICgxJmxlO0wmbGU7MSwwMDApIHdoaWNoIGFyZSB0aGUgbGVuZ3RoIG9mIGEgYmluYXJ5IHNlcXVlbmNlIGFuZCBhIGxlbmd0aCBsb3dlciBib3VuZCwgcmVzcGVjdGl2ZWx5LiBJbiB0aGUgbmV4dCBsaW5lLCBhIHN0cmluZywgYmluYXJ5IHNlcXVlbmNlLCBvZiBsZW5ndGggbiBpcyBnaXZlbi4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCB0aGUgc3RhcnRpbmcgYW5kIGVuZGluZyBpbmRleCBvZiB0aGUgc3Vic2VxdWVuY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Seoul 2009 D번