Компания 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 являются простыми числами, но напомнило, что число является простым, если у него ровно два различных целых положительных делителя.