30785번 - Программируемая змейка 다국어

문제

Компания 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. Помимо этого, соседними являются клетки верхней и нижней строки, а также крайнего левого и крайнего правого столбца, то есть все пары клеток вида (1, i)–(H, i), где i пробегает от 1 до W, и все пары вида (i, 1)–(i, W), где i пробегает от 1 до H.

На поле находится змейка, представляющая собой последовательность клеток A₁, A₂, . . . , A_L, где L — целое положительное число, означающее её длину. Каждая клетка должна встречаться в данной последовательности не более одного раза, при этом любые две клетки, соседние в последовательности, должны являться соседними клетками поля. Несложно заметить, что максимально допустимая длина змейки равняется H · W. Клетка A₁ называется головой змейки.

Игрок управляет только перемещением головы змейки. Для этого он может использовать четыре команды:

• ‘L’ — перемещает голову змейки влево, то есть уменьшает на единицу номер столбца, в котором она находится. Если перед использованием команды голова находится в крайнем левом столбце, то она переносится в крайний правый столбец, оставаясь при этом в той же строке.
• ‘R’ — перемещает голову змейки вправо, то есть увеличивает на единицу номер столбца. Аналогично предыдущей команде, из крайнего правого столбца голова переносится в крайний левый.
• U’ — перемещает голову змейки вверх, то есть уменьшает на единицу номер строки, в которой она находится. Граница обрабатывается так же, как и в предыдущих командах, то есть применение в верхней строке переносит голову змейки в нижнюю строку, не меняя столбец.
• ‘D’ — перемещает голову змейки вниз, то есть увеличивает на единицу номер строки. Соответственно, из нижней строки голова змейки переносится в верхнюю.

Как только игрок использует команду, все клетки, образующие змейку, перемещаются одновременно, при этом голова сдвигается по описанным выше правилам, а все остальные клетки «подтягиваются» за ней, то есть для всех i от 2 до L клетка A_i заменяется на бывшее значение клетки A_i−1. Например, вторая клетка змейки (если она существует, то есть L ⩾ 2) перемещается туда, где находилась голова, третья клетка (если L ⩾ 3) перемещается туда, где находилась вторая, и так далее.

Игра заканчивается, как только змейка врежется сама в себя, то есть на очередном шаге перестанет выполнятся условие уникальности всех клеток. Это может произойти из-за того, что голова переместится в клетку, занимаемую какой-то другой частью змейки. В частности, если змейка состоит хотя бы из трёх клеток, то команда перемещения головы в сторону клетки A₂ приведёт к столкновению, так как в новом положении змейки совпадут клетки A₁ и A₃.

Также в классическом варианте игры присутствует возможность кушать яблоки и увеличивать длину своей змейки, но в рамках данной задачи эта особенность игры не рассматривается.

В новой модификации данной игры от компании Konia игроку больше не требуется регулярно нажимать на кнопки, он должен лишь изначально разместить свою змейку на игровом поле и написать программу действий длины K, то есть задать последовательность из K команд перемещения головы змейки. После запуска змейка будет последовательно выполнять команды, пока не врежется сама в себя. Если змейка успешно выполнит все K команд, то она начинает выполнять их заново в той же последовательности, и так до тех пор, пока не произойдет столкновение или игроку не надоест следить за процессом.

Вам, как ведущему инженеру компании Konia по программированию змеек, поручено решить следующую задачу: для данных различных простых чисел H и W, определяющих размеры поля, а также данной программы игры, определить, змейку какой максимальной длины можно разместить на игровом поле так, что она никогда не врежется сама в себя после запуска игры. Руководство так и не смогло объяснить вам, почему H и W являются простыми числами, но напомнило, что число является простым, если у него ровно два различных целых положительных делителя.

입력

В первой строке ввода содержится три целых числа H, W и K — размеры поля и длина программы (2 ⩽ H, W ⩽ 10⁹ + 9, H ≠ W, 1 ⩽ K ⩽ min{100 000, H · W}).

Обратите внимание: гарантируется, что H и W — различные простые числа.

Во второй строке подряд записаны K символов, задающих последовательность команд. Никакие символы, кроме ‘L’, ‘R’, ‘U’ и ‘D’, в данной строке не встречаются.

출력

Выведите одно число — максимальную длину змейки, которая сможет неограниченно долго перемещаться в соответствии с данной последовательностью команд, ни разу не врезавшись в саму себя.

제한

노트

В первом тесте после выполнения всех четырёх команд голова змейки оказывается в своём стартовом положении, поэтому змейка длиннее четырёх клеток не проживёт больше четырёх ходов.

Во втором тесте правильно расположенная змейка может занять почти всё поле.