시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 44 1 1 2.273%

문제

상근이는 실험용 쥐를 이용해서 실험을 하고 있다. 상근이는 쥐를 N×N개의 정사각형 칸으로 이루어진 우리에 가두었다. 각각의 칸은 빨간색이거나 흰색이다. 행은 위에서부터 1번부터 N번이며, 열은 왼쪽에서부터 1번이다.

쥐는 네 방향(왼쪽, 오른쪽, 위, 아래)으로 이동한다. 하지만, 빨간색을 무서워하기 때문에, 절대로 빨간 칸에는 들어가지 않는다.

이제 쥐를 크기가 K×K인 박스안에 가둔다. 박스의 변은 모두 우리의 변에 평행하다. 박스 안은 매우 어둡지만 쥐는 어디가 빨간색 칸인지 정확하게 알고 있기 때문에 빨간 칸에 들어가지 않는다.

상근이는 박스 안에 있는 쥐의 위치를 볼 수 없고, 박스의 움직임만 밖에서 볼 수 있다. 쥐가 박스의 가장자리를 미는 경우에 박스가 그 방향으로 움직이게 된다.

위의 그림은 예제를 나타낸 것이다. 검정 동그라미는 쥐, 회색 직사각형은 박스를 나타낸다.

박스의 처음 위치와 박스가 움직인 방향이 모두 주어졌을 때, 그러한 움직임을 만드려면 쥐가 최소 몇 번 이동해야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 우리의 크기 N과 박스의 크기 K가 주어진다. (2 ≤ K ≤ 10, K < N ≤ 100)

다음 N개 줄에는 우리의 각 칸이 빨간 칸('r')인지 흰 칸('w')인지 주어진다.

다음 줄에는 박스의 처음 위치 R과 C가 주어지며, 이 좌표는 박스의 왼쪽 위 꼭지점이다. (1 ≤ R, C ≤ N-K+1)

다음 줄에는 박스가 움직인 횟수 M (1 ≤ M ≤ 1,00,000)이 주어진다.

마지막 줄에는 박스가 움직인 방향이 순서대로 주어진다. (L, R, U, D)

출력

첫째 줄에 쥐가 최소 몇 번 움직이면 입력으로 주어진 방향대로 움직이는지 출력한다.

예제 입력

5 3
wwwww
wrwrw
wwwww
wrrrw
wwwww
3 3
2
LU

예제 출력

3

힌트