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$

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 through in one row moving right, or in one column moving down.

• $1 \leq T \leq 1\,000$
• $1 \leq N,M \leq 5\,000$
• Every character of is one of , , and .