Печатные платы являются одной из основ современной электроники. Для разводки печатных плат существует огромное количество программ, а для перенесения готового рисунка на поверхность платы — не меньшее количество методов (порой весьма экзотических). Одним из способов переноса рисунка является использование графопостроителя — устройства, способного вычерчивать на поверхности непрерывные линии. Напишите программу, которая по рисунку печатной платы составит набор команд для графопостроителя, необходимый для вычерчивания этого рисунка.
Графопостроитель работает на квадратной сетке размером $$$n \times m$$$ . Квадраты сетки нумеруются слева направо (первая координата) и сверху вниз (вторая координата). Команда для вычерчивания линии состоит из двух чисел — координат начала линии — и последовательности букв «L», «R», «U», «D», которые прочерчивают линию на одну клетку от текущего положения влево, вправо, вверх или вниз соответственно. Например, команда «3 4 DRUL» нарисует квадрат со стороной 1 и левым верхним углом в координатах (3, 4).
С целью минимизации временных затрат на рисование, программа должна построить набор из минимально возможного количества команд (непрерывных линий). Если таких наборов несколько, то решением считается любой из них. Учтите, что:
Первая строка входных данных содержит целые числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 100$$$) — размер печатной платы. Далее следуют $$$n$$$ строк по $$$m$$$ символов в каждой. Для кодирования рисунка платы используются следующие символы:
Для любой линии на изображении существует начальная и конечная точки. Линия может начинаться и заканчиваться в одной и той же точке — тогда такая точка обозначается как «*». Через один квадрат проходит либо ровно одна линия, либо, если в этом квадрате происходит пересечение нескольких линий, они считаются соединенными, и квадрат содержит знак «*». Прохождение линий через один квадрат без соединения невозможно. Знаки «*» не могут встречаться в соседних клетках (клетках, имеющих общую сторону).
Первая строка выходных данных содержит число $$$k$$$ ($$$0 \leq k \leq 10000$$$) — количество команд. Далее следуют $$$k$$$ строк, каждая из которых описывает отдельную команду. Команда начинается с двух целых чисел $$$x$$$ и $$$y$$$, разделенных пробелом, — координат начала линии. Далее, также через пробел, следует последовательность из заглавных букв «L», «R», «U» или «D», описывающих прочерчиваемую линию. Буквы идут подряд без пробелов. Команда заканчивается переводом строки.
3 4 r--* *... L--*
1 4 3 LLLUURRR
3 4 r--* L--7 *--J
1 1 3 RRRULLLURRR
3 3 r-* |.| L-J
1 3 1 LLDDRRUU
5 5 ..*.. ..|.. *-*-* ..|.. ..*..
2 3 5 UUUU 1 3 RRRR
Обратите внимание, что рисунок платы описывается построчно, а команды используют координаты в формате «столбец строка».