과학자

한 과학자가 실험용 쥐를 N×N개의 정사각형 칸으로 이루어진 우리에 넣었다. 각 칸은 흰색이거나 빨간색이다. 행은 위에서 아래로 1번부터 N번까지, 열은 왼쪽에서 오른쪽으로 1번부터 N번까지 번호가 붙어 있다.

쥐는 왼쪽, 오른쪽, 위, 아래의 네 방향으로 한 칸씩 이동할 수 있다. 빨간색 칸을 무서워하므로 빨간 칸에는 절대 들어가지 않는다.

이제 쥐는 K×K 크기의 상자 안에 있다. 상자의 변은 우리 격자의 변과 평행하다. 상자 안은 매우 어둡지만, 쥐는 어떤 칸이 빨간 칸인지 정확히 알고 있어서 빨간 칸으로 이동하지 않는다.

과학자는 상자 안의 쥐 위치를 볼 수 없고, 밖에서 상자의 움직임만 볼 수 있다. 쥐가 상자의 가장자리에서 바깥쪽으로 한 칸 이동하려고 하면, 상자는 그 방향으로 한 칸 움직이고 쥐도 상자와 함께 그 방향으로 한 칸 이동한다.

그림에서 검은 원은 쥐를, 회색 직사각형은 상자를 나타낸다.

상자의 처음 위치와 이후 상자가 움직인 방향들이 주어질 때, 그 움직임들을 만들기 위해 쥐가 최소 몇 번 이동해야 하는지 구하라.

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

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

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

다음 줄에는 상자가 움직인 횟수 M이 주어진다. (1 ≤ M ≤ 100,000)

마지막 줄에는 상자가 움직인 방향이 순서대로 주어진다. 각 문자는 L, R, U, D 중 하나이다.

입력으로 주어진 방향대로 상자를 움직이게 하려면 쥐가 최소 몇 번 이동해야 하는지 첫째 줄에 출력한다.