Рабочее место участника

Жители одного `N`-этажного дома решили устроить флэш-моб – изобразить ночью на стене дома ползущую "змейку" из `L` светящихся окон, включая и выключая свет в определённом порядке.

Они придумали схему движения змейки, которая представляет собой последовательность шагов R, L, U, D для движения вправо, влево, вверх и вниз соответственно. Если змейка достигает одного из краев стены, она выползает с другого края (если была наверху и ползла вверх – выползает снизу, и т.д.). Змейка должна выполнять один шаг в секунду.

Теперь нужно для каждого окна определить моменты включения и выключения света.

Окна пронумерованы слева направо снизу вверх, начиная с 1. На каждом этаже имеется по `M` окон. В начальный момент времени видна только "голова" змейки, которая находится в первом окне. В течении первых `L` шагов в первом окне появляются последующие части змейки. Перед началом движения свет во всех окнах выключен, по окончании движения он также выключается.

Для каждого окна, в котором хотя бы раз должен зажечься свет, следует вывести его номер и интервалы времени, в течении которых свет должен гореть. Интервалы должны быть отсортированы по возрастанию времени начала. Если следующий интервал начинается сразу по окончании предыдущего, их следует объединить.

В первой строке входного файла содержатся числа `N\ M\ L`. Во второй строке – описания шагов для змейки, записанные подряд без пробелов.

В выходном файле должна содержаться последовательность инструкций для каждого окна. Инструкции состоят из номера окна, количества интервалов, и последовательности интервалов, где каждый интервал описывается начальным и конечным моментом времени, измеренным в секундах.

`1\ ≤\ N\ ≤\ 50`, `1\ ≤\ M\ ≤\ 50`, `1\ ≤\ L\ ≤\ 1000`

Количество шагов находится в диапазоне от 1 до 10000

5 4 4
RRULDDL

1 1  1 4
2 1  2 8
3 1  3 6
6 1  5 8
7 1  4 7
17 1  8 8
18 1  7 8