Задача . E. Порядок

Семен любит порядок. Поэтому, перед тем, как лечь спать, Семен хочет завершить все дела в доме.

Дом Семена сверху выглядит как прямоугольная таблица, состоящая из n строк и n столбцов. Строки таблицы пронумерованы от 1 до n сверху вниз, а столбцы — от 1 до n слева направо. Каждая ячейка этой таблицы — это комната. Парой (i, j) будем обозначать комнату, расположенную на пересечении i-ой строки и j-ого столбца. Про каждую комнату известно, включен ли в ней свет, или нет.

Изначально Семен находится в комнате (x₀, y₀). Он хочет выключить свет во всех комнатах в доме и после этого вернуться в комнату (x₀, y₀). Обозначим комнату, в которой на данный момент находится Семен, (x, y). Чтобы выполнить желаемое, Семен может выполнять следующие действия:

• Формат действия — «1». Во время выполнения этого действия, Семен включает свет в комнате (x, y). Запрещается выполнять действие, если в комнате уже включен свет.
• Формат действия — «2». Во время выполнения этого действия, Семен выключает свет в комнате (x, y). Запрещается выполнять действие, если в комнате уже выключен свет.
• Формат действия — «dir» (dir это символ). Во время выполнения этого действия, Семен перемещается в соседнюю по стороне комнату в направлении dir. Всего Семен может двигаться только в 4-х направлениях: влево, вправо, вверх и вниз (соответственно, dir равен L, R, U, D). Кроме того, Семен может перейти только в комнату, по направлению которой где-то горит свет. Более формально, если обозначить за (nx, ny) комнату, в которую Семен хочет перейти, то должно существовать такое целое число k (k > 0), что существует комната со включенным светом в ячейке (x + (nx - x)k, y + (ny - y)k). Конечно, Семену запрещается выходить за пределы дома.

Помогите Семену, найдите такую последовательность действий, что Семен выполнит желаемое.