시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cclxuXHQyLiBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHVjNmQwIFx1YzgxMFx1YWNmYyBcdWIzYzRcdWNjMjlcdWM4MTBcdWM3NDQgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzNjXHViODVjXHVkNTU4XHViMjk0IFx1Y2Q5NVx1YzVkMCBcdWQzYzlcdWQ1ODlcdWQ1NWMgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YmM5N1x1YzViNFx1YjA5OFx1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWFmYzhcdWM1ZDBcdWMxMWMgXHVjNzc0XHViM2Q5XHVkNTVjIFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHVjNzdjXHViZDgwXHViOTdjIFx1YzljMFx1YzZjY1x1YzExYyBcdWJiMzhcdWM4MWNcdWM3NTggMlx1YWMxYyBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHVhYzhjIFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzYzRcdWNjMjlcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjIEFcdWM2NDAgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQSwgQiAmbGU7IDQwMDApPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjYzNkXHVjNjAxXHVjNzc0XHVhYzAwIFx1Yzc3NFx1YjNkOVx1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyA4MDAwKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWM3NzRcdWIzZDlcdWQ1NWMgXHViYzI5XHViYzk1XHVjNzc0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1Yzc0MCBSLCBcdWM2N2NcdWNhYmRcdWM3NDAgTCwgXHVjNzA0XHViMjk0IFUsIFx1YzU0NFx1Yjc5OFx1YjI5NCBEXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTU4XHViMDk4XHViOTdjIFx1YzljMFx1YzZjY1x1YzU3YyBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWM3ODVcdWI4MjVcdWI5Y2MgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgS1x1YzY0MCBMXHVjNzQ0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAoMSAmbGU7IEsgJmxlOyBMICZsZTsgTikgS1x1YzY0MCBMXHVjNzQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjNzc0XHViM2Q5IFx1YmMyOVx1YmM5NSBcdWM5MTEgS1x1YmM4OFx1YzlmOFx1YmQ4MFx1ZDEzMCBMXHViYzg4XHVjOWY4XHVhZTRjXHVjOWMwXHViOTdjIFx1YzljMFx1YzZjY1x1YzU3YyBcdWQ1NWNcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMyNDUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNUkVcdTAxN2RBIiwiZGVzY3JpcHRpb24iOiI8cD5Ud28gd2hvbGUgbnVtYmVycyBBIGFuZCBCIGFuZCBhIGNvb3JkaW5hdGUgc3lzdGVtIGluIGEgcGxhbmUgYXJlIGdpdmVuLiBUaGUgb3JpZ2luICgwLDApIGlzIGxhYmVsZWQgJmxkcXVvO3N0YXJ0JnJkcXVvOyBhbmQgYSBwb2ludCB3aXRoIGNvb3JkaW5hdGVzIChBLEIpIGlzIGxhYmVsZWQgJmxkcXVvO2VuZCZyZHF1bzsuIEEgZmlndXJlIGlzIHBsYWNlZCBhdCB0aGUgb3JpZ2luLiBBIHNlcXVlbmNlIG9mIHN0ZXBzIHRoZSBmaWd1cmUgaGFzIHRvIHBlcmZvcm0gaXMgYWxzbyBnaXZlbi4gRWFjaCBzdGVwIGNvbnNpc3RzIG9mIGEgbW92ZSBmcm9tIGEgY3VycmVudCBwb2ludCB0byBhbnkgb2YgdGhlIGZvdXIgY2xvc2VzdCBwb2ludHMgd2l0aCBpbnRlZ2VyIGNvb3JkaW5hdGVzIGx5aW5nIHVwLCBkb3duLCBsZWZ0IGFuZCByaWdodC4gRm9yIGV4YW1wbGUsIG1vdmluZyBvbmUgc3RlcCB1cCBtZWFucyBnb2luZyBmcm9tICh4LHkpIHRvICh4LHkrMSk7IG1vdmluZyBvbmUgc3RlcCBsZWZ0IG1lYW5zIGdvaW5nIGZyb20gKHgseSkgdG8gKHgtMSx5KS4gSWYgdGhlIGZpZ3VyZSBpcyBsb2NhdGVkIGF0IHRoZSBwb2ludCAoeCx5KSB0aGVuIHdlIGNhbGN1bGF0ZSBpdHMgZGlzdGFuY2UgZnJvbSB0aGUgZW5kIHBvaW50IGJ5IHRoZSBmb3JtdWxhJm5ic3A7PFwvcD5cclxuXHJcbjxwPmQoKHgseSksKEEsQikpID0gYWJzKHgtQSkgKyBhYnMoeS1CKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgZmluZCBhbmQgcmVtb3ZlIGEgY29uc2VjdXRpdmUgc3Vic2VxdWVuY2Ugb3V0IG9mIHRoZSBnaXZlbiBzZXF1ZW5jZSBvZiBzdGVwcyB1bmRlciB0aGUgZm9sbG93aW5nIHR3byBjb25kaXRpb25zOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSBkaXN0YW5jZSBiZXR3ZWVuIHRoZSBlbmQgcG9pbnQgYW5kIHRoZSBsYXN0IHBvc2l0aW9uIG9mIHRoZSBmaWd1cmUgaXMgbWluaW1hbCBwb3NzaWJsZS4mbmJzcDs8XC9saT5cclxuXHQ8bGk+VGhlIGZpZ3VyZSBuZXZlciBsZWF2ZXMgdGhlIHJlY3RhbmdsZSB3aG9zZSBkaWFnb25hbCBwb2ludHMgYXJlIHRoZSBvcmlnaW4gYW5kIHRoZSBlbmQgcG9pbnQgYW5kIHdob3NlIHNpZGVzIGFyZSBwYXJhbGxlbCB3aXRoIHRoZSBjb29yZGluYXRlIGF4ZXMuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGZpbGUgY29udGFpbnMgdHdvIHdob2xlIG51bWJlcnMgQSBhbmQgQiwgdGhlIGNvb3JkaW5hdGVzIG9mIGVuZCBwb2ludCBzZXBhcmF0ZWQgYnkgYSBzcGFjZSBjaGFyYWN0ZXIsIDEgJmxlOyBBLCBCICZsZTsgNDAwMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIGEgd2hvbGUgbnVtYmVyIE4sIHRoZSBudW1iZXIgb2Ygc3RlcHMsIDEgJmxlOyBOICZsZTsgODAwMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHRoaXJkIGxpbmUgY29udGFpbnMgYSBzZXF1ZW5jZSBvZiBsZW5ndGggTiBvZiBjaGFyYWN0ZXJzLiBFYWNoIGNoYXJhY3RlciBvZiBhIHNlcXVlbmNlIGNhbiBiZSBhbnkgb2YgY2hhcmFjdGVycyAmIzM5O1ImIzM5OyAtIHJpZ2h0ICwgJiMzOTtVJiMzOTsgLSB1cCwgJiMzOTtMJiMzOTsgLSBsZWZ0LCAmIzM5O0QmIzM5OyAmbmRhc2g7IGRvd24uIFRoZSBzZXF1ZW5jZSBkZWZpbmVzIHRoZSBzZXF1ZW5jZSBvZiBzdGVwcyB0aGUgZmlndXJlIGhhcyB0byBwZXJmb3JtLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiBFYWNoIHNldCBvZiBpbnB1dCBkYXRhIHdpbGwgcmVxdWlyZSByZW1vdmFsIG9mIGF0IGxlYXN0IG9uZSBzdGVwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBmaWxlIHNob3VsZCBjb250YWluIHR3byB3aG9sZSBudW1iZXJzIEsgYW5kIEwgc2VwYXJhdGVkIGJ5IG9uZSBzcGFjZSBjaGFyYWN0ZXIsIDEgJmxlOyBLICZsZTsgTCAmbGU7IE4sIG1lYW5pbmcgdGhhdCBhbGwgc3RlcHMgYmVnaW5uaW5nIHdpdGggS3RoIGFuZCBlbmRpbmcgd2l0aCBMdGggc2hvdWxkIGJlIHJlbW92ZWQgZnJvbSB0aGUgc2VxdWVuY2Ugb2Ygc3RlcHMgZ2l2ZW4gaW4gdGhlIGlucHV0IGZpbGUuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d