프로그래밍 가능한 뱀

Konia는 저가형 모바일 기기를 만드는 회사인데 최근 시장 점유율이 떨어지고 있습니다. 회사를 살리려고 이사회는 Konia의 모든 기기에서 돌아가는 가장 유명한 게임인 뱀 게임을 바꾸기로 했습니다. 그렇습니다, 또 뱀 게임입니다.

게임은 H개 행과 W개 열로 이루어진 격자 판에서 진행됩니다. 행은 위에서 아래로 1부터 H까지, 열은 왼쪽에서 오른쪽으로 1부터 W까지 번호를 붙입니다. 칸 A는 $(A_r, A_c)$로 나타내며, $A_r$은 행 번호, $A_c$는 열 번호입니다. 두 칸 A와 B는 $|A_r - B_r| + |A_c - B_c| = 1$이면 인접합니다. 맨 위 행과 맨 아래 행의 칸끼리, 맨 왼쪽 열과 맨 오른쪽 열의 칸끼리도 인접합니다. 즉 모든 $i$(1부터 W까지)에 대해 $(1, i)$와 $(H, i)$가 인접하고, 모든 $i$(1부터 H까지)에 대해 $(i, 1)$과 $(i, W)$가 인접합니다.

뱀은 칸의 수열 $A_1, A_2, \ldots, A_L$입니다. L은 뱀의 길이인 양의 정수입니다. 수열 안에서 같은 칸이 두 번 나오면 안 되고, 수열에서 이웃한 두 칸은 판에서도 인접해야 합니다. 가능한 최대 길이는 $H \times W$입니다. $A_1$을 머리라고 합니다.

플레이어가 조작하는 것은 머리뿐이며, 명령은 네 가지입니다.

• L: 머리를 왼쪽으로 한 열 옮깁니다. 머리가 가장 왼쪽 열에 있으면 같은 행의 가장 오른쪽 열로 옮깁니다.
• R: 머리를 오른쪽으로 한 열 옮깁니다. 머리가 가장 오른쪽 열에 있으면 같은 행의 가장 왼쪽 열로 옮깁니다.
• U: 머리를 위로 한 행 옮깁니다. 머리가 맨 위 행에 있으면 같은 열의 맨 아래 행으로 옮깁니다.
• D: 머리를 아래로 한 행 옮깁니다. 머리가 맨 아래 행에 있으면 같은 열의 맨 위 행으로 옮깁니다.

명령을 하나 실행하면 뱀의 모든 칸이 동시에 움직입니다. 머리는 위 규칙대로 움직이고, 나머지 칸은 앞 칸이 있던 자리로 따라갑니다. 즉 2 이상인 모든 $i$에 대해 $A_i$는 $A_{i-1}$이 있던 자리로 이동합니다. 예를 들어 $L \ge 2$이면 두 번째 칸은 머리가 있던 자리로 가고, $L \ge 3$이면 세 번째 칸은 두 번째 칸이 있던 자리로 갑니다.

뱀이 자기 자신과 부딪히는 순간 게임이 끝납니다. 즉 이동 뒤에 모든 칸이 서로 달라야 한다는 조건이 깨지면 끝납니다. 머리가 뱀의 다른 부분이 차지한 칸으로 이동하면 이에 해당합니다. 특히 뱀 길이가 3 이상이면 머리를 $A_2$ 쪽으로 옮기는 명령은 충돌을 일으킵니다. 이동 후 $A_1$과 $A_3$이 같은 칸에 놓이기 때문입니다.

원래 게임에는 사과를 먹고 길어지는 기능이 있지만, 이 문제에서는 다루지 않습니다.

새 버전에서는 버튼을 계속 누를 필요가 없습니다. 플레이어는 뱀을 판 위에 한 번 놓고, 길이 K인 프로그램, 즉 머리의 이동 명령 K개를 씁니다. 게임이 시작되면 뱀은 명령을 차례로 수행합니다. K개 명령을 충돌 없이 모두 마치면 같은 순서로 처음부터 다시 수행합니다. 충돌이 일어나거나 플레이어가 지켜보기를 멈출 때까지 이 과정이 반복됩니다.

여러분은 Konia의 뱀 프로그래밍 수석 엔지니어로서 다음 문제를 풀어야 합니다. 판의 크기를 정하는 서로 다른 소수 H와 W, 그리고 명령 프로그램이 주어집니다. 게임을 시작한 뒤 자기 자신과 절대 부딪히지 않도록 놓을 수 있는 뱀의 최대 길이를 구하세요. 회사는 H와 W가 왜 소수여야 하는지 설명하지 못했지만, 소수는 양의 약수가 정확히 두 개인 수라는 점은 알려 주었습니다.

첫 줄에 정수 H, W, K가 주어집니다. 판의 크기와 프로그램 길이입니다. $2 \le H, W \le 10^9 + 9$, $H \ne W$, $1 \le K \le \min\{100\,000, H \times W\}$입니다.

H와 W는 서로 다른 소수라고 보장됩니다.

둘째 줄에는 공백 없이 K개의 문자가 이어서 주어집니다. 각 문자는 L, R, U, D 중 하나입니다.

명령 수열을 따라 자기 자신과 부딪히지 않고 무한히 움직일 수 있는 뱀의 최대 길이를 한 줄에 출력합니다.

첫 번째 테스트에서는 명령 네 개를 모두 실행하면 머리가 시작 칸으로 돌아옵니다. 따라서 길이가 4칸보다 긴 뱀은 4번 이동하기 전에 부딪힙니다.

두 번째 테스트에서는 뱀을 올바르게 놓으면 판의 거의 전체를 차지할 수 있습니다.