다다스 문자열 지우기

문자열 da가 한 번 이상 반복된 뒤 문자 s로 끝나는 문자열을 다다스 문자열이라고 한다. 예를 들어 das와 dadadas는 다다스 문자열이다.

문자 d, a, s로 이루어진 $N \times M$ 격자가 있다.

한 번의 연산으로, 다음 두 조건을 모두 만족하는 한 행 또는 한 열의 연속한 구간을 골라 그 구간의 모든 칸을 지울 수 있다.

• 고른 구간의 모든 칸이 아직 지워지지 않았다.
• 구간의 문자들을 행에서는 왼쪽에서 오른쪽으로, 열에서는 위에서 아래로 읽었을 때 다다스 문자열이 된다.

즉, 이미 지워진 칸을 포함하는 구간을 고를 수 없으며, 이미 지워진 칸을 사이에 두고 떨어져 있는 칸들을 하나의 구간으로 간주할 수도 없다.

한 칸은 두 번 지울 수 없다. 모든 칸을 지울 수 있는지 판별하고, 가능하다면 연산 방법 하나를 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

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

$G_i$는 격자의 $i$번째 행을 나타내는 길이 $M$의 문자열이다.

각 테스트 케이스마다 모든 칸을 지울 수 없다면 NO를 출력한다.

모든 칸을 지울 수 있다면 첫째 줄에 YES, 둘째 줄에 연산 횟수 $K$를 출력한다. 이어지는 $K$개의 줄에 각 연산을 $r_1\ c_1\ r_2\ c_2$의 형식으로 출력한다. 이는 $(r_1,c_1)$에서 $(r_2,c_2)$까지 같은 행에서 오른쪽으로 또는 같은 열에서 아래쪽으로 이어지는 모든 칸을 지운다는 뜻이다.

가능한 답이 여러 가지라면 아무거나 출력해도 된다.

• $1 \leq T \leq 1\,000$
• $1 \leq N,M \leq 5\,000$
• $G_i$의 각 문자는 d, a, s 중 하나이다.
• 모든 테스트 케이스에 대한 $NM$의 합은 $2\,000\,000$ 이하이다.