In his years of youth rebellion, Humbertov Moralov decided to paint the walls of this university. But un- like the rest of the revel young people, Moralov in- vented a robot to paint the wall for him. The robot can execute two simple instructions to draw lines, namely: • hline r c1 c2: draw a horizontal line in the row r between columns c1 and c2. • vline c r1 r2: draw a vertical line in the col- umn c between rows r1 and r2. Now Moralov wants you to write a program that given the piece of rebel art to paint, outputs a program for the robot with the minimum number of instructions to paint the wall. Hint: Some algorithms that you may find useful to solve this problem may have a theoretical complexity analysis that seems too high for the given input size. Remember that these complexity analysis are usually done thinking on the worst case, and many algorithms run much faster in practice. The input file for this problem was not constructed to break any particular solution in terms of complexity. Input The input consists of several test cases. Each test case begins with a line with two integers R and C corresponding to the number of rows and columns of the design to paint in the wall. Then R lines follow each with C characters. A character ‘’ means that the cell needs to be painted, and ‘.’ means that the cell should be left unpainted. • 1 ≤ R, C ≤ 800 Output For each test case print in one line a single integer n corresponding to the minimum number of instruc- tions to paint the wall. Then n lines should follow with the instructions to actually paint the wall. If there are multiple solutions output any of them. Sample Input 57 ..... ..... .*****. ..... ....*.
2/2 Sample Output 3 vline 2 1 5 vline 6 1 5 hline 3 2 6