화살표 미로 (Hard)

입력 제한을 제외하면 난이도에 따라 문제가 달라지지 않는다.

민규는 25년간의 외로운 수련 끝에 드디어 마법사가 되었다. 마법사가 된 민규의 꿈은 마법처럼 멋진 테마파크를 짓는 것이었다. 민규는 테마파크의 첫 상품으로 "화살표 미로"를 공개했다.

화살표 미로는 평범한 미로와 다른 점이 많다. 이 미로는 R×C개의 방으로 이루어져 있다. 모든 방은 사방이 벽으로 막혀 있어 서로 이동할 수 없고, 각 방은 저마다 완전히 다른 테마의 화려한 볼거리로 꾸며져 있다.

<그림 1> 화살표 미로의 지도

사방이 벽으로 막혀 있다면 어떻게 다른 방으로 이동할 수 있을까? 민규는 각 방마다 특별한 마법진을 그려, 마법진에 그려진 화살표 방향으로 한 칸 순간이동할 수 있도록 설계했다! 미로의 가장 바깥벽은 마그마로 둘러싸여 있어서, 가장 바깥벽을 넘어 미로 자체를 탈출하지는 못한다.

고객들은 미로의 가장 왼쪽 위인 (1,1)방의 입구에서 시작해 다양한 방을 경험하고, 가장 오른쪽 아래인 (R,C)방의 출구에 도착해야 미로를 마칠 수 있다. 그러지 못하면 영원히 화살표 미로를 헤매게 된다! 당연하게도 처음 민규가 그려 둔 마법진의 화살표 방향에 따라서는 출구에 가지 못할 수도 있다.

민규는 고객들이 화살표 미로를 안전하게 즐기도록 입구에서 특별한 주문서를 판다. 주문서에는 화살표를 반시계 방향으로 회전시키는 'L 주문서'와 시계 방향으로 회전시키는 'R 주문서' 두 종류가 있다. 주문서를 사용하면 해당 방향으로 화살표가 90도 회전한다. 여러 장의 주문서를 한 마법진에 연달아 사용해 180도, 270도 회전하도록 만들 수도 있다. 민규는 수익을 극대화하기 위해 L 주문서와 R 주문서를 각각 한 장씩 묶은 세트로만 판매하고 있다.

화살표 미로를 이용하는 고객은 미로에 입장해야만 지도를 받을 수 있다. 그래서 영원히 헤매지 않으려면 울며 겨자 먹기로 대량의 주문서 세트를 사야 했다. 화살표 미로를 즐겨 이용하던 민규의 친구 준서도 이런 불편을 겪고 있었다.

준서 : 아니, 적어도 지금 가진 걸론 충분한지 아닌지는 말해 줘야 하는 거 아니야 ??

준서의 불평에 지친 민규는 준서에게만 특별히, 준서가 가진 주문서 세트로 출구까지 갈 수 있는지를 묻는 질문에 "Yes" 또는 "No"로 단 한 번 답해 주기로 했다. 정확하게 답하는 일은 민규에게 매우 어려우므로, 질문에 대신 답하는 프로그램을 당신에게 의뢰했다.

첫째 줄에는 미로의 행 R, 열 C, 준서가 가진 주문서 세트의 개수 K가 주어진다.

둘째 줄부터 R줄에 걸쳐 화살표 미로의 지도가 입력된다. 각 줄은 "UDLR"로만 이루어진 길이 C의 문자열이며, U는 위, D는 아래, L은 왼쪽, R은 오른쪽으로 이동할 수 있는 마법진을 뜻한다.

준서의 질문에 대한 답을 "Yes" 또는 "No"로 출력한다.

1 ≤ R, C ≤ 150

0 ≤ K ≤ 1500