E. Печатная плата
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Печатные платы являются одной из основ современной электроники. Для разводки печатных плат существует огромное количество программ, а для перенесения готового рисунка на поверхность платы — не меньшее количество методов (порой весьма экзотических). Одним из способов переноса рисунка является использование графопостроителя — устройства, способного вычерчивать на поверхности непрерывные линии. Напишите программу, которая по рисунку печатной платы составит набор команд для графопостроителя, необходимый для вычерчивания этого рисунка.

Графопостроитель работает на квадратной сетке размером $$$n \times m$$$ . Квадраты сетки нумеруются слева направо (первая координата) и сверху вниз (вторая координата). Команда для вычерчивания линии состоит из двух чисел — координат начала линии — и последовательности букв «L», «R», «U», «D», которые прочерчивают линию на одну клетку от текущего положения влево, вправо, вверх или вниз соответственно. Например, команда «3 4 DRUL» нарисует квадрат со стороной 1 и левым верхним углом в координатах (3, 4).

С целью минимизации временных затрат на рисование, программа должна построить набор из минимально возможного количества команд (непрерывных линий). Если таких наборов несколько, то решением считается любой из них. Учтите, что:

  • Любая клетка платы либо не содержит линии, либо содержит одну линию, либо две пересекающихся (точку пересечения);
  • Линия может начинаться и заканчиваться в одной и той же точке;
  • Если две линии начинаются в одной точке, то их можно объединить в одну линию;
  • Длина линии не может быть меньше 2 (линия не может соединять 2 соседних квадрата);
  • Линия или линии не могут начинаться или заканчиваться в соседних клетках (клетки считаются соседними, если имеют общую сторону);
  • Линия не может быть проведена поверх уже существующей.
Входные данные

Первая строка входных данных содержит целые числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 100$$$) — размер печатной платы. Далее следуют $$$n$$$ строк по $$$m$$$ символов в каждой. Для кодирования рисунка платы используются следующие символы:

  • «.» («Точка», код 0x2E) — пустой квадрат;
  • «*» («Звездочка», код 0x2A) — Начало или конец линии, либо точка, где сходятся больше двух линий;
  • «-» («Минус», код 0x2D) - Горизонтальная линия;
  • «|» («Вертикальная черта», код 0x7С) — Вертикальная линия;
  • «L» («Заглавная L», код 0x4C) — Линия, соединяющая верхнюю и правую клетки;
  • «J» («Заглавная J», код 0x4A) — Линия, соединяющая верхнюю и левую клетки;
  • «r» («Строчная r», код 0x72) — Линия, соединяющая нижнюю и правую клетки;
  • «7» («Цифра 7», код 0x37) — Линия, соединяющая нижнюю и левую клетки.

Для любой линии на изображении существует начальная и конечная точки. Линия может начинаться и заканчиваться в одной и той же точке — тогда такая точка обозначается как «*». Через один квадрат проходит либо ровно одна линия, либо, если в этом квадрате происходит пересечение нескольких линий, они считаются соединенными, и квадрат содержит знак «*». Прохождение линий через один квадрат без соединения невозможно. Знаки «*» не могут встречаться в соседних клетках (клетках, имеющих общую сторону).

Выходные данные

Первая строка выходных данных содержит число $$$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
Примечание

Обратите внимание, что рисунок платы описывается построчно, а команды используют координаты в формате «столбец строка».