Description

Farmer John has $N (1 \le N \le 10^5)$ cows, each of which is either Guernsey or Holstein. They stand in a row along a horizontal line, occupying positions $1 \cdots N$.

Since the cows are hungry, FJ decides to plant grass patches at some positions among $1 \cdots N$. Guernseys and Holsteins prefer different types of grass, so if Farmer John decides to plant grass at a position, he must choose either the type preferred by Guernseys or the type preferred by Holsteins—he cannot plant both types at the same position. Each planted grass patch can feed an unlimited number of cows of the corresponding breed.

Each cow is willing to move at most $K (0 \le K \le N - 1)$ positions to reach a grass patch. Determine the minimum number of grass patches needed to feed all cows. In addition, output one planting plan that feeds all cows using the minimum number of patches. Any plan that satisfies the conditions is considered correct.

Input Format

Each input contains $T$ test cases, each describing an arrangement of cows. The first line contains $T (1 \le T \le 10)$. Then $T$ test cases follow.

For each test case, the first line contains $N$ and $K$. The second line contains a string of length $N$, where the $i$-th character indicates the breed of the $i$-th cow ($\texttt{G}$ for Guernsey, $\texttt{H}$ for Holstein).

Output Format

For each of the $T$ test cases, output two lines. The first line should contain the minimum number of grass patches needed to feed all cows. The second line should contain a string of length $N$ representing one optimal planting plan. The $i$-th character corresponds to position $i$: output $\texttt{.}$ if no grass is planted, $\texttt{G}$ if grass for Guernseys is planted, and $\texttt{H}$ if grass for Holsteins is planted. Any valid plan will be accepted.

6
5 0
GHHGG
5 1
GHHGG
5 2
GHHGG
5 3
GHHGG
5 4
GHHGG
2 1
GH

5
GHHGG
3
.GH.G
2
..GH.
2
...GH
2
...HG
2
HG

Hint

Explanation for Sample 1

Note that for some test cases, there are multiple optimal planting plans using the minimum number of patches. For example, in the fourth test case, the following is another acceptable answer:

This plan plants a Guernsey-feeding patch at position $2$ and a Holstein-feeding patch at position $3$. This uses the minimum number of patches and ensures that all cows are within $3$ positions of their preferred grass.

Testdata Properties

• Testdata $2$–$4$ satisfies $N \le 10$.
• Testdata $5$–$8$ satisfies $N \le 40$.
• Testdata $9$–$12$ satisfies $N \le 10^5$.

Translated by ChatGPT 5