Table Drawing

Statement

We have a blank sheet in a spreadsheet. We need to draw a fairly complicated table layout onto the sheet by drawing lines along some specific borders of some specific cells.

Our spreadsheet app only supports the basic set of border-drawing operations. For each of the operations, you start by selecting an arbitrary rectangle in the sheet. Then you have the following options:

• T, B, L, R: Draw a line along the top/bottom/left/right side of the selected rectangle. You can do multiple of these operations at once. (E.g., choosing all four options will draw the entire border of the selected rectangle.)
• A: Draw all possible lines both on the boundary and inside the selected rectangle.
• E: Erase everything both on the boundary and inside the selected rectangle.

Input format

The input file contains a single test case. The test case starts with a line containing two numbers \(r\) and \(c\): the number of rows and columns in your sheet.

The rest of the input file contains an ASCII art drawing of the desired table layout: \(2r+1\) lines, each containing \(2c+1\) printable characters. The ASCII art uses ‘+’ for all cell corners, ‘-’ and ‘|’ for horizontal and vertical lines along cell borders, and ‘.’ (period) everywhere else.

Output format

The first line of your output should contain the number \(n\) of operations you want to perform on an empty spreadsheet.

The rest of your output should consist of \(n\) lines describing these operations (one per line, in chronological order).

The description of each operation must have the form “\(r_{min}\) \(r_{max}\) \(c_{min}\) \(c_{max}\) \(cmd\)”, where:

• \(0\leq r_{min}\leq r_{max}\leq r-1\) specify the inclusive range of rows for the rectangle you want to select
• \(0\leq c_{min}\leq c_{max}\leq c-1\) specify the inclusive range of columns for the rectangle you want to select
• \(cmd\) is either A, or E, or a non-empty combination of the letters TBLR.

Note that it is not allowed to select rows and columns outside the sheet.

Also carefully note the order in which the four coordinates are presented: first the range of rows, then the range of columns.

Special rule

Resubmissions for this problem do not generate penalty minutes.

Subproblem T1 (100 points, private)

Input file: T1.in

Constraints: \(r = c = 201\).

In order to score any points, you need to find a valid way of drawing exactly the given table using \(25\,000\) or fewer commands. The formula that converts the number of commands to your score: \(score = \min( 100, 10 + 220\,000 / n )\)

Your score will be rounded to two decimal places.

The scoring formula was chosen in a way that makes it possible to score 100 points even without having to find an optimal solution.

Notes

The only subproblem in this problem is private. This means that during the contest you will be able to see the evaluation results (so you’ll know whether your solution was accepted and also its score) but the public ranklist will not show your score: any submission will appear as “potential 100 points” instead.

The limit on the number of submissions is still in place for subproblem T1.

Example

3 4
+-+-+-+.+
|.|.|...|
+-+-+-+.+
..|.....|
+-+-+-+.+
|.|.|.|.|
+-+-+-+-+

4
0 0 0 2 A
0 1 3 3 E
0 2 1 3 RBL
2 2 0 2 A