뽜밤뽜밤-! 아리스는 메이드 용사로 전직했습니다!

밀레니엄 사이언스 스쿨 엔지니어부의 히비키는 튜링 머신과 비슷한 원리로 작동하는 로봇 청소기를 발명했습니다.

히비키는 로봇 청소기로 $H \times W$ 직사각형 격자 모양의 게임개발부 부실을 청소하려고 합니다. 격자칸의 좌표는 $(r,c)$로 나타낼 수 있으며, 아래로 갈수록 $r$이 증가하고 오른쪽으로 갈수록 $c$가 증가합니다. 가장 왼쪽 위 칸의 좌표는 $(0,0)$, 오른쪽 아래 칸의 좌표는 $(H-1,W-1)$입니다.

처음에 모든 칸은 먼지로 뒤덮여 있습니다. 로봇 청소기는 격자 한 칸 크기이며, 바라보는 방향으로 전진하거나 제자리에서 회전할 수 있습니다.

로봇 청소기의 전원을 켜면 다음과 같이 작동합니다. 먼저 $H \times W$ 크기의 규칙표 $A$와 $B$를 만듭니다. 규칙표의 각 칸은 청소할 영역의 격자칸에 대응됩니다. 규칙표에는 회전 각도가 적혀 있습니다.

이후 로봇 청소기는 매 단위 시간마다 다음과 같은 이동을 반복합니다.

• 현재 칸에 먼지가 있다면 먼지를 제거합니다.
• 방금 먼지를 제거했다면 규칙표 $A$를, 먼지를 제거하지 않았다면 규칙표 $B$를 참조합니다. 규칙표에서 현재 좌표에 적힌 만큼 시계방향으로 회전합니다.
• 바라보는 방향으로 한 칸 전진합니다.

이동을 마친 후에, 로봇 청소기가 영역 밖으로 벗어났다면 작동을 중지합니다. 또한, 지금부터 위의 과정을 아무리 반복해도 더이상 먼지를 제거할 수 없는 경우에도 작동을 중지합니다.

메이드 용사로 전직한 아리스는 히비키의 로봇청소기를 보고, 용사 수행을 위해 로봇 청소기와 똑같은 원리로 동작하여 게임개발부 부실을 청소하려고 합니다. 방의 구조와 아리스의 처음 위치, 그리고 규칙표가 주어집니다. 아리스가 청소를 시작하고 마칠 때까지 이동한 횟수를 출력하세요.

입력 형식

첫 번째 줄에 방의 크기를 나타내는 $H, W$가 주어집니다. $(1 \le H, W \le 1\,024)$

두 번째 줄에 아리스의 처음 위치를 나타내는 $R, C, D$가 주어집니다. 아리스의 좌표는 $(R,C)$이고, 위쪽을 기준으로 시계방향으로 $90D$도만큼 회전한 방향을 바라보고 있음을 나타냅니다. $(0 \le R < H;$ $0 \le C < W;$ $0 \le D \le 3)$

다음 $H$개의 줄에 규칙표 $A$가 주어집니다.

다음 $H$개의 줄에 규칙표 $B$가 주어집니다.

규칙표는 길이 $W$인 문자열 $H$개로 주어집니다. 문자열은 $0$ 이상 $3$ 이하의 숫자로 구성되며, 숫자 $d$는 $90d$도 회전을 의미합니다.

출력 형식

아리스가 청소를 시작하고 마칠 때까지 이동한 횟수를 출력하세요.

예제 입력 1

3 4
1 3 0
1122
1003
3330
1200
3031
3332

예제 출력 1

13

예제 입력 2

3 4
1 3 0
1122
1003
3330
1200
1031
3332

예제 출력 2

9