Feeding the Cows with Minimal Grass Patches

Farmer John has N cows lined up at positions \(1,2,\dots,N\). Each cow is either a Guernsey (denoted by 'G') or a Holstein (denoted by 'H'). Because the two breeds prefer different types of grass, if Farmer John plants a grass patch at a position, he must choose a single grass type at that position (i.e. he cannot plant both types on the same position). Each patch, once planted, can feed an unlimited number of cows of the matching breed.

Every cow is willing to move at most \(K\) positions from its original position to reach a patch. In other words, a cow at position \(i\) can be fed by a patch planted at position \(p\) only if \(|i-p|\le K\).

Your task is to determine the minimum number of patches needed to feed all the cows and to output one valid planting plan using this minimum number of patches. In the planting plan, output a string of length \(N\) where the i-th character is:

• G if a patch for Guernsey-preferred grass is planted at position i,
• H if a patch for Holstein-preferred grass is planted at position i,
• . if no patch is planted at position i.

Note on the use of patches: A patch planted for one breed cannot feed cows of the other breed. Also, a patch planted at position \(p\) can feed any cow of the matching breed whose position \(i\) satisfies \(|i-p| \le K\).

inputFormat

The input consists of two lines. The first line contains two integers \(N\) and \(K\) (with \(1\le N\le 10^5\) and \(0\le K\le N-1\)). The second line is a string of length \(N\) composed solely of the characters G and H, representing the breed of the cow at positions \(1\) through \(N\) respectively.

outputFormat

On the first line, output the minimum number of grass patches needed to feed all cows. On the second line, output a valid planting plan – a string of length \(N\) where the i-th character is G if a patch with Guernsey‐preferred grass is planted at that position, H if a patch with Holstein‐preferred grass is planted there, or . if no patch is planted.

Any valid plan that uses the minimum number of patches is accepted.

sample

5 1
GHGHG

3
.GHG.