거리

창영이는 꿈속에서 좌표평면을 걸었다. 처음 위치는 원점 (0, 0)이고, 도착점은 (A, B)이다. 창영이는 항상 정수 좌표 위에만 서 있으며, 크기는 무시할 수 있을 만큼 작다.

한 번 이동할 때는 현재 점에서 상하좌우로 인접한 네 점 중 하나로 이동한다. 예를 들어 (x, y)에서 위로 이동하면 (x, y + 1), 왼쪽으로 이동하면 (x - 1, y)가 된다.

현재 위치가 (x, y)일 때 도착점 (A, B)까지의 거리는 다음과 같이 정의한다.

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

창영이는 도착점으로 이동하던 중 꿈에서 깼고, 꿈속에서 움직인 방법을 모두 적어 두었다. 이제 이 이동 방법에서 비어 있지 않은 연속 구간 하나를 지우려고 한다. 남은 이동을 앞에서부터 순서대로 수행했을 때 다음 두 조건을 만족해야 한다.

• 마지막 위치와 도착점 사이의 거리가 가능한 한 작아야 한다.
• 이동하는 모든 순간에 원점과 도착점을 꼭짓점으로 하는, 좌표축에 평행한 직사각형 밖으로 나가면 안 된다. 즉 항상 0 <= x <= A이고 0 <= y <= B여야 한다.

주어진 이동 방법에서 어떤 연속 구간을 지워야 하는지 구하라.

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

둘째 줄에 이동 횟수 N이 주어진다. (1 <= N <= 8000)

셋째 줄에 길이 N의 문자열이 주어진다. 각 문자는 이동 방향을 나타내며, 오른쪽은 R, 왼쪽은 L, 위는 U, 아래는 D이다.

입력은 적어도 하나의 연속 구간을 지워 조건을 만족시킬 수 있도록 주어진다.

첫째 줄에 K와 L을 공백으로 구분하여 출력한다. (1 <= K <= L <= N)

이는 입력으로 주어진 이동 방법 중 K번째 이동부터 L번째 이동까지를 지운다는 뜻이다.