Erasing Dadas Strings

A string consisting of one or more repetitions of da, followed by the character s, is called a Dadas string. For example, das and dadadas are Dadas strings.

You are given an $N \times M$ grid consisting of the characters d, a, and s.

In one operation, you may choose a contiguous segment of a single row or a single column and erase all cells in that segment, provided that both of the following conditions hold:

• None of the cells in the chosen segment has been erased before.
• When the characters in the segment are read from left to right for a row, or from top to bottom for a column, they form a Dadas string.

In particular, a chosen segment may not contain an already erased cell, and cells separated by an already erased cell cannot be treated as part of the same segment.

Each cell can be erased at most once. Determine whether it is possible to erase all cells, and if so, find one sequence of operations that does so.

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N\ M$ $G_1$ $G_2$ $\vdots$ $G_N$

$G_i$ is a string of length $M$ describing row $i$ of the grid.

For each test case, print NO if it is impossible to erase every cell.

Otherwise, print YES on the first line and the number of operations $K$ on the second line. On each of the next $K$ lines, print an operation as $r_1\ c_1\ r_2\ c_2$. It erases every cell from $(r_1,c_1)$ through $(r_2,c_2)$ in one row moving right, or in one column moving down.

If there are multiple solutions, print any of them.

• $1 \leq T \leq 1\,000$
• $1 \leq N,M \leq 5\,000$
• Every character of $G_i$ is one of d, a, and s.
• The sum of $NM$ over all test cases does not exceed $2\,000\,000$.