Problem Description

Translated from COCI 2019/2020 Contest #6 T4. Skandi

Dragica is not only the captain of a local semi-professional bowling team but also an enthusiastic chef and one of the top crossword puzzle players in Croatia. A crossword puzzle is played on a grid of size $N \times M$. At the start of the game, some cells are already filled with letters, serving as the starting points for up to two clues. Players need to fill in the remaining cells based on the given hints, either horizontally to the right or vertically downwards. A clue's answer is defined as the sequence of cells from the clue's starting point in the direction specified by the hint until the grid's boundary or another clue's starting point is reached. If the cell to the right of a clue's starting point is empty, there is a horizontal clue; similarly, if the cell below the starting point is empty, there is a vertical clue.

Dragica knows the answers but is a bit lazy and wants you to help him find the minimum number of clues he needs to answer to complete a given crossword puzzle.

Input Format

The first line contains two space-separated integers $N$ and $M$, as described in the problem statement.

The next $N$ lines each contain $M$ characters, either 0 or 1, where 0 indicates an empty cell to be filled, and 1 indicates a cell already filled with a character, serving as the starting point for up to two clues. It is guaranteed that there is at least one 0 in the input, and the first row and the first column are all 1.

Output Format

The first line should output the minimum number of answers $X$ needed to complete the crossword puzzle.

The next $X$ lines should each contain a clue in the format r c dir, where r is the row number of the clue, c is the column number of the clue, and dir is either DESNO (right in Croatian) or DOLJE (down in Croatian), indicating the direction of the clue.

If there are multiple solutions, output any one.

Sample Input and Output

Sample Input #1

4 5
11111
10000
10000
10000

Sample Output #1

3
2 1 DESNO
3 1 DESNO
4 1 DESNO

Sample Input #2

6 4
1111
1011
1000
1011
1010
1000

Sample Output #2

4
1 2 DOLJE
4 4 DOLJE
5 3 DOLJE
3 1 DESNO

Sample Input #3

9 8
11111111
10000000
10001000
10010001
11100001
10100110
10001000
10100001
10010001

Sample Output #3

14
5 2 DOLJE
5 8 DOLJE
8 3 DOLJE
2 1 DESNO
3 1 DESNO
3 5 DESNO
4 1 DESNO
4 4 DESNO
5 3 DESNO
6 3 DESNO
7 1 DESNO
7 5 DESNO
8 3 DESNO
9 4 DESNO

Notes/Hints

Sample #3 Explanation:

The following images show the crossword puzzle from the sample, where black cells indicate cells that are already filled with characters at the start. The tables below the images show the horizontal and vertical clues provided. Note that cells filled with characters can be the starting points for zero, one (e.g., clues 8 and 13), or two (e.g., clues 10 and 12) clues. To solve it, you need to know at least 14 clues' answers. Try to see if you can solve it!

Data Range:

For $100\%$ of the data, $2 \le N, M \le 500$.

Subtask constraints are as follows:

见题面 Input 部分

见题面 Output 部分