407381: GYM102780 E Printed circuit board

Printed circuit boards are one of the key notions of modern electronics. There are a huge number of programs for working with the printed circuit boards, and for transferring the complete drawing to the surface of the board, there exist quite a lot of methods (sometimes very exotic). One way to transfer a picture is to use a plotter, a device that can draw continuous lines on the surface. Write a program that, according to the printed circuit board drawing, will make up a set of commands for the plotter to draw this drawing.

The plotter works on a square grid of $$$n \times m$$$ size. The grid squares are numbered from left to right (first coordinate), and from top to bottom (second coordinate). The command for drawing a line consists of two numbers — the coordinates of the beginning of the line, and a sequence of letters "L", "R", "U", "D", which draw a line one cell from the current position to the left, right, up or down, respectively. For example, the "3 4 DRUL" command will draw a square with side 1 and the upper left corner at coordinates 3 4.

In order to minimize the time spent on drawing, the program should build a set of the minimum possible number of commands (continuous lines). If there are several such sets, then any of them is to be considered a solution.

Please note that:

• Any cell of the board either does not contain a line, or contains one line, or two intersecting lines (intersection point);
• A line can begin and end at the same point;
• If two lines start at one point, then they can be combined into one line;
• The line length cannot be less than 2 (the line cannot connect 2 adjacent squares);
• A line or lines cannot begin or end in neighboring cells (the cells are considered neighboring if they have a common side);
• A line cannot be drawn over an existing one.

The first line of input contains integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 100$$$) — the size of the printed circuit board. This is followed by $$$n$$$ lines of $$$m$$$ characters in each. The following characters are used to encode a board picture:

• "." ("Point", code 0x2E) — empty (blank) square;
• "*" ("Asterisk", code 0x2A) — The beginning or end of the line, or the point where more than two lines meet;
• "-" ("Minus", code 0x2D) - Horizontal line;
• "|" ("Vertical bar", code 0x7C) — Vertical line;
• "L" ("Capital L", code 0x4C) — The line connecting the upper and the right cells;
• "J" ("Capital J", code 0x4A) — A line connecting the upper and the left cells;
• "r" ("Lowercase r", code 0x72) — The line connecting the lower and the right cells;
• "7" ("Digit 7", code 0x37) — The line connecting the lower and the left cells.

For any line in the image, there is a starting and a final point. The line can begin and end at the same point, then such a point is indicated as "*". Through one square either one line passes, or, if several lines intersect in this square, then they are considered connected, and the square contains the "*" sign. The passing of lines through one square without a connection is not possible. The signs "*" cannot be found in the neighboring cells (cells having a common side).

The first line of the output contains the number $$$k$$$ ($$$0 \leq k \leq 10000$$$) — the number of commands. This is followed by $$$k$$$ lines, each of which describes a separate command. The command begins with two integers $$$x$$$ and $$$y$$$, separated by a blank space, — the coordinates of the beginning of the line. Further, also through a blank space, comes a sequence of capital letters "L", "R", "U" or "D", describing the line to be drawn. Letters go in a row without spaces. The command ends with a line feed.

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

Please, note that the board drawing is described in a line by line fashion and the commands use the "column row" coordinates.