3245번 - 거리 스페셜 저지

창영이는 꿈 속에서 문제를 푼다. 오늘 창영이는 좌표평면을 걸어다니는 꿈을 꾸었다. 창영이는 현재 시작점 (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번째까지를 지워야 한다는 뜻이다.