Feeding the Cows

Farmer John has $N$ ($1 \le N \le 10^5$) cows. Each cow is either a Guernsey or a Holstein. The cows stand in a horizontal line at positions $1$ through $N$.

The cows are hungry, so Farmer John plants grassy patches on some of the positions $1$ through $N$. Guernseys and Holsteins prefer different grass. If he plants grass at a position, it must be either Guernsey-preferred grass or Holstein-preferred grass. He cannot plant both at the same position. Each patch can feed an unlimited number of cows of the matching breed.

Each cow is willing to move a maximum of $K$ ($0 \le K \le N-1$) positions to reach a patch. Find the minimum number of patches needed to feed all the cows. Also print a configuration of patches that uses this minimum number. Any configuration that satisfies the conditions is correct.

The first line contains $T$ ($1 \le T \le 10$), the number of test cases. Each test case starts with a line containing $N$ and $K$. The next line contains a string of length $N$, where the $i$th character is the breed of the $i$th cow: G for Guernsey and H for Holstein.

For each test case, print two lines. The first line is the minimum number of patches needed to feed the cows. The second line is a string of length $N$. The $i$th character is '.' if there is no patch at position $i$, 'G' if there is a Guernsey-preferred patch, and 'H' if there is a Holstein-preferred patch. Any valid configuration with the minimum number of patches is accepted.

Some test cases have more than one valid configuration with the minimum number of patches. For example, in the fourth test case, another acceptable answer is:

.GH..

This places a Guernsey-preferred patch at position 2 and a Holstein-preferred patch at position 3. It uses the optimal number of patches, and every cow is within 3 positions of a patch it prefers.