시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6MTAwJVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPlx1Yzc3OFx1YjM3MVx1YzJhNDxcL3RoPlxyXG5cdFx0XHQ8dGg+MTxcL3RoPlxyXG5cdFx0XHQ8dGg+MjxcL3RoPlxyXG5cdFx0XHQ8dGg+MzxcL3RoPlxyXG5cdFx0XHQ8dGg+NDxcL3RoPlxyXG5cdFx0XHQ8dGg+NTxcL3RoPlxyXG5cdFx0XHQ8dGg+NjxcL3RoPlxyXG5cdFx0XHQ8dGg+NzxcL3RoPlxyXG5cdFx0XHQ8dGg+ODxcL3RoPlxyXG5cdFx0XHQ8dGg+OTxcL3RoPlxyXG5cdFx0XHQ8dGg+MTA8XC90aD5cclxuXHRcdFx0PHRoPjExPFwvdGg+XHJcblx0XHRcdDx0aD4xMjxcL3RoPlxyXG5cdFx0XHQ8dGg+MTM8XC90aD5cclxuXHRcdFx0PHRoPjE0PFwvdGg+XHJcblx0XHRcdDx0aD4xNTxcL3RoPlxyXG5cdFx0XHQ8dGg+MTY8XC90aD5cclxuXHRcdFx0PHRoPjE3PFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5cdWMyMThcdWM1ZjQ8XC90aD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlx1Yzc3NFx1YzljNFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzc0NCBcdWI1NGMsIFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWQ1NThcdWQ1NWNcdWM3NzQgN1x1Yzc3NFx1Yjc3Y1x1YmE3NCBcdWQzYzlcdWFkZTBcdWM3NzQgXHVjZDVjXHViMzAwXHVjNzc4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NDAgWzcsMTRdXHVhYzAwIFx1YjQxOFx1YWNlMCwgXHVkM2M5XHVhZGUwXHVjNzQwIDZcLzhcdWM3NzRcdWIyZTQuIFx1ZDU1OFx1ZDU1Y1x1Yzc3NCA1XHVjNzc4IFx1YWNiZFx1YzZiMCwgXHVkM2M5XHVhZGUwXHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1Yzc3OCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzQwIFs3LDExXVx1Yzc3NCBcdWI0MThcdWFjZTAsIFx1ZDNjOVx1YWRlMFx1Yzc0MCA0XC81XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjOWM0XHVjMjE4XHVjNWY0XHVhY2ZjIFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWQ1NThcdWQ1NWMgTFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVjODAxXHVjNWI0XHViM2M0IExcdWM3NzggXHViYWE4XHViNGUwIFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjQgXHVjOTExXHVjNWQwXHVjMTFjIFx1ZDNjOVx1YWRlMFx1Yzc3NCBcdWNkNWNcdWIzMDBcdWM3NzggXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVhYzE5XHVjNzQwIFx1ZDNjOVx1YWRlMFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWIyOTQgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzc4IFx1YWNiZFx1YzZiMCwgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YzllN1x1Yzc0MCBcdWFjODNcdWM3NDQgXHVjYzNlXHVjNzNjXHViYTc0IFx1YjQxY1x1YjJlNC4gXHVhZTM4XHVjNzc0XHVhYzAwIFx1YzllN1x1Yzc0MCBcdWFjODNcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQsIFx1YzJkY1x1Yzc5MSBcdWM3MDRcdWNlNThcdWFjMDAgXHVjNTVlXHVjMTFjXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWNjM2VcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc3NFx1YzljNFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzQgbigxICZsZTsgbiAmbGU7IDEwMCwwMDApXHVhY2ZjIFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWQ1NThcdWQ1NWMgTCgxICZsZTsgTCAmbGU7IDEsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZTM4XHVjNzc0XHVhYzAwIG5cdWM3NzggXHVjNzc0XHVjOWM0XHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWI5YzhcdWIyZTQgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjNzA0XHVjZTU4XHVjNjQwIFx1YjA1ZCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijg5MjUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBdmVyYWdlIiwiZGVzY3JpcHRpb24iOiI8cD5BIEROQSBzZXF1ZW5jZSBjb25zaXN0cyBvZiBmb3VyIGxldHRlcnMsIEEsIEMsIEcsIGFuZCBULiBUaGUgR0MtcmF0aW8gb2YgYSBETkEgc2VxdWVuY2UgaXMgdGhlIG51bWJlciBvZiBDcyBhbmQgR3Mgb2YgdGhlIHNlcXVlbmNlIGRpdmlkZWQgYnkgdGhlIGxlbmd0aCBvZiB0aGUgc2VxdWVuY2UuIEdDLXJhdGlvIGlzIGltcG9ydGFudCBpbiBnZW5lIGZpbmRpbmcgYmVjYXVzZSBETkEgc2VxdWVuY2VzIHdpdGggcmVsYXRpdmVseSBoaWdoIEdDLXJhdGlvcyBtaWdodCBiZSBnb29kIGNhbmRpZGF0ZXMgZm9yIHRoZSBzdGFydGluZyBwYXJ0cyBvZiBnZW5lcy4gR2l2ZW4gYSB2ZXJ5IGxvbmcgRE5BIHNlcXVlbmNlLCByZXNlYXJjaGVycyBhcmUgdXN1YWxseSBpbnRlcmVzdGVkIGluIGxvY2F0aW5nIGEgc3Vic2VxdWVuY2Ugd2hvc2UgR0MtcmF0aW8gaXMgbWF4aW11bSBvdmVyIGFsbCBzdWJzZXF1ZW5jZXMgb2YgdGhlIHNlcXVlbmNlLiBTaW5jZSBzaG9ydCBzdWJzZXF1ZW5jZXMgd2l0aCBoaWdoIEdDLXJhdGlvcyBhcmUgc29tZXRpbWVzIG1lYW5pbmdsZXNzIGluIGdlbmUgZmluZGluZywgYSBsZW5ndGggbG93ZXIgYm91bmQgaXMgZ2l2ZW4gdG8gZW5zdXJlIHRoYXQgYSBsb25nIHN1YnNlcXVlbmNlIHdpdGggaGlnaCBHQy1yYXRpbyBjb3VsZCBiZSBmb3VuZC4gSWYsIGluIGEgRE5BIHNlcXVlbmNlLCBhIDAgaXMgYXNzaWduZWQgdG8gZXZlcnkgQSBhbmQgVCBhbmQgYSAxIHRvIGV2ZXJ5IEMgYW5kIEcsIHRoZSBETkEgc2VxdWVuY2UgaXMgdHJhbnNmb3JtZWQgaW50byBhIGJpbmFyeSBzZXF1ZW5jZSBvZiB0aGUgc2FtZSBsZW5ndGguIEdDLXJhdGlvcyBpbiB0aGUgRE5BIHNlcXVlbmNlIGFyZSBub3cgZXF1aXZhbGVudCB0byBhdmVyYWdlcyBpbiB0aGUgYmluYXJ5IHNlcXVlbmNlLiZuYnNwOzxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6MTAwJVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPlBvc2l0aW9uIEluZGV4PFwvdGg+XHJcblx0XHRcdDx0aD4xPFwvdGg+XHJcblx0XHRcdDx0aD4yPFwvdGg+XHJcblx0XHRcdDx0aD4zPFwvdGg+XHJcblx0XHRcdDx0aD40PFwvdGg+XHJcblx0XHRcdDx0aD41PFwvdGg+XHJcblx0XHRcdDx0aD42PFwvdGg+XHJcblx0XHRcdDx0aD43PFwvdGg+XHJcblx0XHRcdDx0aD44PFwvdGg+XHJcblx0XHRcdDx0aD45PFwvdGg+XHJcblx0XHRcdDx0aD4xMDxcL3RoPlxyXG5cdFx0XHQ8dGg+MTE8XC90aD5cclxuXHRcdFx0PHRoPjEyPFwvdGg+XHJcblx0XHRcdDx0aD4xMzxcL3RoPlxyXG5cdFx0XHQ8dGg+MTQ8XC90aD5cclxuXHRcdFx0PHRoPjE1PFwvdGg+XHJcblx0XHRcdDx0aD4xNjxcL3RoPlxyXG5cdFx0XHQ8dGg+MTc8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPlNlcXVlbmNlPFwvdGg+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5Gb3IgdGhlIGJpbmFyeSBzZXF1ZW5jZSBhYm92ZSwgaWYgdGhlIGxlbmd0aCBsb3dlciBib3VuZCBpcyA3LCB0aGUgbWF4aW11bSBhdmVyYWdlIGlzIDZcLzggd2hpY2ggaGFwcGVucyBpbiB0aGUgc3Vic2VxdWVuY2UgWzcsMTRdLiBJdHMgbGVuZ3RoIGlzIDgsIHdoaWNoIGlzIGdyZWF0ZXIgdGhhbiB0aGUgbGVuZ3RoIGxvd2VyIGJvdW5kIDcuIElmIHRoZSBsZW5ndGggbG93ZXIgYm91bmQgaXMgNSwgdGhlbiB0aGUgc3Vic2VxdWVuY2UgWzcsMTFdIGdpdmVzIHRoZSBtYXhpbXVtIGF2ZXJhZ2UgNFwvNS4gVGhlIGxlbmd0aCBpcyA1IHdoaWNoIGlzIGVxdWFsIHRvIHRoZSBsZW5ndGggbG93ZXIgYm91bmQuIEZvciB0aGUgc3Vic2VxdWVuY2UgWzcsMTFdLCA3IGlzIGl0cyBzdGFydGluZyBpbmRleCBhbmQgMTEgaXMgaXRzIGVuZGluZyBpbmRleC4mbmJzcDs8YnIgXC8+XHJcbiZuYnNwOzxiciBcLz5cclxuR2l2ZW4gYSBiaW5hcnkgc2VxdWVuY2UgYW5kIGEgbGVuZ3RoIGxvd2VyIGJvdW5kIEwsIHdyaXRlIGEgcHJvZ3JhbSB0byBmaW5kIGEgc3Vic2VxdWVuY2Ugb2YgdGhlIGJpbmFyeSBzZXF1ZW5jZSB3aG9zZSBsZW5ndGggaXMgYXQgbGVhc3QgTCBhbmQgd2hvc2UgYXZlcmFnZSBpcyBtYXhpbXVtIG92ZXIgYWxsIHN1YnNlcXVlbmNlcyBvZiB0aGUgYmluYXJ5IHNlcXVlbmNlLiBJZiB0d28gb3IgbW9yZSBzdWJzZXF1ZW5jZXMgaGF2ZSB0aGUgbWF4aW11bSBhdmVyYWdlLCB0aGVuIGZpbmQgdGhlIHNob3J0ZXN0IG9uZTsgYW5kIGlmIHR3byBvciBtb3JlIHNob3J0ZXN0IHN1YnNlcXVlbmNlcyB3aXRoIHRoZSBtYXhpbXVtIGF2ZXJhZ2UgZXhpc3QsIHRoZW4gZmluZCB0aGUgb25lIHdpdGggdGhlIHNtYWxsZXN0IHN0YXJ0aW5nIGluZGV4LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlcnMgbiAoMSZsZTtuJmxlOzEwMCwwMDApIGFuZCBMICgxJmxlO0wmbGU7MSwwMDApIHdoaWNoIGFyZSB0aGUgbGVuZ3RoIG9mIGEgYmluYXJ5IHNlcXVlbmNlIGFuZCBhIGxlbmd0aCBsb3dlciBib3VuZCwgcmVzcGVjdGl2ZWx5LiBJbiB0aGUgbmV4dCBsaW5lLCBhIHN0cmluZywgYmluYXJ5IHNlcXVlbmNlLCBvZiBsZW5ndGggbiBpcyBnaXZlbi4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCB0aGUgc3RhcnRpbmcgYW5kIGVuZGluZyBpbmRleCBvZiB0aGUgc3Vic2VxdWVuY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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