\(N \times M\) 격자에서 시작 위치와 장애물, 이동 명령을 받아 모든 명령을 처리한 뒤 (최종 행, 최종 열, 실제 이동 횟수)를 반환하는 함수 trace_path를 작성하시오. U, D, L, R은 각각 위, 아래, 왼쪽, 오른쪽으로 한 칸 이동하는 명령이다. 격자 밖으로 나가거나 장애물이 있는 칸으로 이동하는 명령은 무시한다.

함수 원형은 주어지지 않는다. 설명과 아래의 호출 코드를 보고 함수의 매개변수와 반환값을 직접 설계한다.

함수를 사용하는 코드

작성한 함수는 아래 코드와 함께 실행된다.

n, m = map(int, input().split())
start = tuple(map(int, input().split()))
k = int(input())
obstacles = {tuple(map(int, input().split())) for _ in range(k)}
commands = input()

result = trace_path(n, m, start, obstacles, commands)
print(*result)
print(type(result))

위 코드가 정상적으로 동작하도록 함수를 직접 정의한다. 제출할 때는 작성한 함수의 정의 전체만 제출한다.

입력

첫째 줄에 \(N\), \(M\)이 주어진다. 둘째 줄에 시작 행과 열이 주어진다. 셋째 줄에 장애물 수 k가 주어지고, 다음 k개 줄에 장애물의 행과 열이 주어진다. 마지막 줄에 이동 명령 문자열이 주어진다. 모든 좌표는 0부터 시작한다.

• \(1 \le N,M \le 1,000\)
• \(0 \le k \le 100,000\)
• 명령 문자열의 길이는 \(0\) 이상 \(100,000\) 이하이다.
• 장애물 좌표는 서로 다르며 시작 위치에는 장애물이 없다.

출력

최종 행, 최종 열, 실제로 이동한 횟수를 출력한다. 함수는 세 정수를 담은 tuple을 반환해야 한다.

마지막 줄에는 함수가 반환한 값의 자료형을 출력한다.

예제 입력 1

3 4
1 1
1
1 2
RRDLU

예제 출력 1

1 0 3
<class 'tuple'>

예제 입력 2

3 3
0 0
0
RRDDLLUU

예제 출력 2

0 0 8
<class 'tuple'>