Задача E. Флэш-моб ≡

Условие

Жители одного 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