시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 18 4 4 36.364%

문제

창영이는 꿈 속에서 문제를 푼다. 오늘 창영이는 좌표평면을 걸어다니는 꿈을 꾸었다. 창영이는 현재 시작점 (0,0)에 있고, 도착점 (A,B)로 이동하려고 한다. 또한, 창영이는 정수 좌표 위에만 서있고, 크기는 매우 작아서 무시할 수 있다.

한 번 이동할 때, 현재 점에서 인접한 4개의 점(위, 아래, 왼쪽 오른쪽)으로 이동할 수 있다. 예를 들어, (x,y)에서 위로 이동하는 것은 (x, y+1)로 이동하는 것이고, 왼쪽으로 이동하는 것은 (x-1, y)로 이동하는 것이다.

창영이가 (x,y)에 있다면, 끝 점과의 거리를 다음과 같이 구할 수 있다.

d((x, y), (A, B)) = abs(x-A) + abs(y-B)

창영이는 시작점에서 도착점으로 이동하던 중에 꿈에서 깼고, 꿈에서 이동한 방법을 모두 적어놓았다.

이제 이동한 방법에서 연속된 일부를 지워 다음과 같은 2가지 조건을 만족하게 하려고 한다.

1. 도착점과 창영이가 마지막으로 도착한 점 사이의 거리는 최소가 되어야 한다.

2. 창영이는 원 점과 도착점을 꼭짓점으로하는 축에 평행한 직사각형을 벗어나면 안 된다.

창영이가 꿈에서 이동한 방법이 주어졌을 때, 연속된 일부를 지워서 문제의 2개 조건을 만족하게 하는 프로그램을 작성하시오.

입력

첫째 줄에 도착점의 좌표 A와 B가 주어진다. (1 ≤ A, B ≤ 4000)

둘째 줄에는 창영이가 이동한 방법의 수 N이 주어진다. (1 ≤ N ≤ 8000)

셋째 줄에는 창영이가 이동한 방법이 순서대로 주어진다. 오른쪽은 R, 왼쪽은 L, 위는 U, 아래는 D이다.

적어도 하나를 지워야 문제의 조건을 만족하는 입력만 주어진다.

출력

첫째 줄에 K와 L을 공백으로 구분하여 출력한다. (1 ≤ K ≤ L ≤ N) K와 L은 입력으로 주어진 이동 방법 중 K번째부터 L번째까지를 지워야 한다는 뜻이다.

예제 입력 1

2 3
5
RURRR

예제 출력 1

3 4
W3sicHJvYmxlbV9pZCI6IjMyNDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjNzBcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWFmYzggXHVjMThkXHVjNWQwXHVjMTFjIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWQ0N2NcdWIyZTQuIFx1YzYyNFx1YjI5OCBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHVjODhjXHVkNDVjXHVkM2M5XHViYTc0XHVjNzQ0IFx1YWM3OFx1YzViNFx1YjJlNFx1YjJjOFx1YjI5NCBcdWFmYzhcdWM3NDQgXHVhZmI4XHVjNWM4XHViMmU0LiBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHVkNjA0XHVjN2FjIFx1YzJkY1x1Yzc5MVx1YzgxMCAoMCwwKVx1YzVkMCBcdWM3ODhcdWFjZTAsIFx1YjNjNFx1Y2MyOVx1YzgxMCAoQSxCKVx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWI2MTBcdWQ1NWMsIFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM4MTVcdWMyMTggXHVjODhjXHVkNDVjIFx1YzcwNFx1YzVkMFx1YjljYyBcdWMxMWNcdWM3ODhcdWFjZTAsIFx1ZDA2Y1x1YWUzMFx1YjI5NCBcdWI5ZTRcdWM2YjAgXHVjNzkxXHVjNTQ0XHVjMTFjIFx1YmIzNFx1YzJkY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWQ1NWMgXHViYzg4IFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWI1NGMsIFx1ZDYwNFx1YzdhYyBcdWM4MTBcdWM1ZDBcdWMxMWMgXHVjNzc4XHVjODExXHVkNTVjIDRcdWFjMWNcdWM3NTggXHVjODEwKFx1YzcwNCwgXHVjNTQ0XHViNzk4LCBcdWM2N2NcdWNhYmQgXHVjNjI0XHViOTc4XHVjYWJkKVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgKHgseSlcdWM1ZDBcdWMxMWMgXHVjNzA0XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgKHgsIHkrMSlcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YWNlMCwgXHVjNjdjXHVjYWJkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgKHgtMSwgeSlcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjYzNkXHVjNjAxXHVjNzc0XHVhYzAwICh4LHkpXHVjNWQwIFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHViMDVkIFx1YzgxMFx1YWNmY1x1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWFkNmNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0ZCgoeCwgeSksIChBLCBCKSkgPSBhYnMoeC1BKSArIGFicyh5LUIpPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWMyZGNcdWM3OTFcdWM4MTBcdWM1ZDBcdWMxMWMgXHViM2M0XHVjYzI5XHVjODEwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjM1OCBcdWM5MTFcdWM1ZDAgXHVhZmM4XHVjNWQwXHVjMTFjIFx1YWU3Y1x1YWNlMCwgXHVhZmM4XHVjNWQwXHVjMTFjIFx1Yzc3NFx1YjNkOVx1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3NDQgXHViYWE4XHViNDUwIFx1YzgwMVx1YzViNFx1YjE5M1x1YzU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzc0XHVjODFjIFx1Yzc3NFx1YjNkOVx1ZDU1YyBcdWJjMjlcdWJjOTVcdWM1ZDBcdWMxMWMgXHVjNWYwXHVjMThkXHViNDFjIFx1Yzc3Y1x1YmQ4MFx1Yjk3YyBcdWM5YzBcdWM2Y2MgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCAyXHVhYzAwXHVjOWMwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWFjOGMgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0MS4gXHViM2M0XHVjYzI5XHVjODEwXHVhY2ZjIFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMgXHViM2M0XHVjYzI5XHVkNTVjIFx1YzgxMCBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1YWMwMCBcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQyLiBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHVjNmQwIFx1YzgxMFx1YWNmYyBcdWIzYzRcdWNjMjlcdWM4MTBcdWM3NDQgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzNjXHViODVjXHVkNTU4XHViMjk0IFx1Y2Q5NVx1YzVkMCBcdWQzYzlcdWQ1ODlcdWQ1NWMgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YmM5N1x1YzViNFx1YjA5OFx1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWNjM2RcdWM2MDFcdWM3NzRcdWFjMDAgXHVhZmM4XHVjNWQwXHVjMTFjIFx1Yzc3NFx1YjNkOVx1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNWYwXHVjMThkXHViNDFjIFx1Yzc3Y1x1YmQ4MFx1Yjk3YyBcdWM5YzBcdWM2Y2NcdWMxMWMgXHViYjM4XHVjODFjXHVjNzU4IDJcdWFjMWMgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YWM4YyBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViM2M0XHVjYzI5XHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1YyBBXHVjNjQwIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEEsIEIgJmxlOyA0MDAwKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWM3NzRcdWIzZDlcdWQ1NWMgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgODAwMCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNjM2RcdWM2MDFcdWM3NzRcdWFjMDAgXHVjNzc0XHViM2Q5XHVkNTVjIFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NDAgUiwgXHVjNjdjXHVjYWJkXHVjNzQwIEwsIFx1YzcwNFx1YjI5NCBVLCBcdWM1NDRcdWI3OThcdWIyOTQgRFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWM5YzBcdWM2Y2NcdWM1N2MgXHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjNzg1XHViODI1XHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEtcdWM2NDAgTFx1Yzc0NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gKDEgJmxlOyBLICZsZTsgTCAmbGU7IE4pIEtcdWM2NDAgTFx1Yzc0MCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1Yzc3NFx1YjNkOSBcdWJjMjlcdWJjOTUgXHVjOTExIEtcdWJjODhcdWM5ZjhcdWJkODBcdWQxMzAgTFx1YmM4OFx1YzlmOFx1YWU0Y1x1YzljMFx1Yjk3YyBcdWM5YzBcdWM2Y2NcdWM1N2MgXHVkNTVjXHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMjQ1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTVJFXHUwMTdkQSIsImRlc2NyaXB0aW9uIjoiPHA+VHdvIHdob2xlIG51bWJlcnMgQSBhbmQgQiBhbmQgYSBjb29yZGluYXRlIHN5c3RlbSBpbiBhIHBsYW5lIGFyZSBnaXZlbi4gVGhlIG9yaWdpbiAoMCwwKSBpcyBsYWJlbGVkICZsZHF1bztzdGFydCZyZHF1bzsgYW5kIGEgcG9pbnQgd2l0aCBjb29yZGluYXRlcyAoQSxCKSBpcyBsYWJlbGVkICZsZHF1bztlbmQmcmRxdW87LiBBIGZpZ3VyZSBpcyBwbGFjZWQgYXQgdGhlIG9yaWdpbi4gQSBzZXF1ZW5jZSBvZiBzdGVwcyB0aGUgZmlndXJlIGhhcyB0byBwZXJmb3JtIGlzIGFsc28gZ2l2ZW4uIEVhY2ggc3RlcCBjb25zaXN0cyBvZiBhIG1vdmUgZnJvbSBhIGN1cnJlbnQgcG9pbnQgdG8gYW55IG9mIHRoZSBmb3VyIGNsb3Nlc3QgcG9pbnRzIHdpdGggaW50ZWdlciBjb29yZGluYXRlcyBseWluZyB1cCwgZG93biwgbGVmdCBhbmQgcmlnaHQuIEZvciBleGFtcGxlLCBtb3Zpbmcgb25lIHN0ZXAgdXAgbWVhbnMgZ29pbmcgZnJvbSAoeCx5KSB0byAoeCx5KzEpOyBtb3Zpbmcgb25lIHN0ZXAgbGVmdCBtZWFucyBnb2luZyBmcm9tICh4LHkpIHRvICh4LTEseSkuIElmIHRoZSBmaWd1cmUgaXMgbG9jYXRlZCBhdCB0aGUgcG9pbnQgKHgseSkgdGhlbiB3ZSBjYWxjdWxhdGUgaXRzIGRpc3RhbmNlIGZyb20gdGhlIGVuZCBwb2ludCBieSB0aGUgZm9ybXVsYSZuYnNwOzxcL3A+XHJcblxyXG48cD5kKCh4LHkpLChBLEIpKSA9IGFicyh4LUEpICsgYWJzKHktQikuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGZpbmQgYW5kIHJlbW92ZSBhIGNvbnNlY3V0aXZlIHN1YnNlcXVlbmNlIG91dCBvZiB0aGUgZ2l2ZW4gc2VxdWVuY2Ugb2Ygc3RlcHMgdW5kZXIgdGhlIGZvbGxvd2luZyB0d28gY29uZGl0aW9uczombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgZGlzdGFuY2UgYmV0d2VlbiB0aGUgZW5kIHBvaW50IGFuZCB0aGUgbGFzdCBwb3NpdGlvbiBvZiB0aGUgZmlndXJlIGlzIG1pbmltYWwgcG9zc2libGUuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlRoZSBmaWd1cmUgbmV2ZXIgbGVhdmVzIHRoZSByZWN0YW5nbGUgd2hvc2UgZGlhZ29uYWwgcG9pbnRzIGFyZSB0aGUgb3JpZ2luIGFuZCB0aGUgZW5kIHBvaW50IGFuZCB3aG9zZSBzaWRlcyBhcmUgcGFyYWxsZWwgd2l0aCB0aGUgY29vcmRpbmF0ZSBheGVzLiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBmaWxlIGNvbnRhaW5zIHR3byB3aG9sZSBudW1iZXJzIEEgYW5kIEIsIHRoZSBjb29yZGluYXRlcyBvZiBlbmQgcG9pbnQgc2VwYXJhdGVkIGJ5IGEgc3BhY2UgY2hhcmFjdGVyLCAxICZsZTsgQSwgQiAmbGU7IDQwMDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBhIHdob2xlIG51bWJlciBOLCB0aGUgbnVtYmVyIG9mIHN0ZXBzLCAxICZsZTsgTiAmbGU7IDgwMDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zIGEgc2VxdWVuY2Ugb2YgbGVuZ3RoIE4gb2YgY2hhcmFjdGVycy4gRWFjaCBjaGFyYWN0ZXIgb2YgYSBzZXF1ZW5jZSBjYW4gYmUgYW55IG9mIGNoYXJhY3RlcnMgJiMzOTtSJiMzOTsgLSByaWdodCAsICYjMzk7VSYjMzk7IC0gdXAsICYjMzk7TCYjMzk7IC0gbGVmdCwgJiMzOTtEJiMzOTsgJm5kYXNoOyBkb3duLiBUaGUgc2VxdWVuY2UgZGVmaW5lcyB0aGUgc2VxdWVuY2Ugb2Ygc3RlcHMgdGhlIGZpZ3VyZSBoYXMgdG8gcGVyZm9ybS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogRWFjaCBzZXQgb2YgaW5wdXQgZGF0YSB3aWxsIHJlcXVpcmUgcmVtb3ZhbCBvZiBhdCBsZWFzdCBvbmUgc3RlcC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgZmlsZSBzaG91bGQgY29udGFpbiB0d28gd2hvbGUgbnVtYmVycyBLIGFuZCBMIHNlcGFyYXRlZCBieSBvbmUgc3BhY2UgY2hhcmFjdGVyLCAxICZsZTsgSyAmbGU7IEwgJmxlOyBOLCBtZWFuaW5nIHRoYXQgYWxsIHN0ZXBzIGJlZ2lubmluZyB3aXRoIEt0aCBhbmQgZW5kaW5nIHdpdGggTHRoIHNob3VsZCBiZSByZW1vdmVkIGZyb20gdGhlIHNlcXVlbmNlIG9mIHN0ZXBzIGdpdmVuIGluIHRoZSBpbnB1dCBmaWxlLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==