소에게 풀 주기

농부 존은 $N$마리($1 \le N \le 10^5$)의 소를 기른다. 각 소의 품종은 Guernsey 또는 Holstein이다. 소들은 위치 $1$부터 $N$까지 일렬로 서 있다.

소들이 배고파서 농부 존은 위치 $1$부터 $N$ 중 일부에 풀밭을 조성한다. Guernsey와 Holstein은 선호하는 풀이 다르다. 위치에 풀을 심는다면 Guernsey용 풀이나 Holstein용 풀 중 하나여야 하며, 같은 위치에 두 종류를 함께 심을 수는 없다. 각 풀밭은 맞는 품종의 소를 무제한으로 먹일 수 있다.

각 소는 풀밭에 닿기 위해 최대 $K$($0 \le K \le N-1$)칸까지 움직일 수 있다. 모든 소에게 먹이를 주는 데 필요한 풀밭의 최소 개수를 구하라. 또한 그 최소 개수를 사용하는 풀밭 배치를 하나 출력하라. 조건을 만족하는 배치라면 어떤 것이든 정답이다.

첫 줄에 테스트 케이스의 수 $T$($1 \le T \le 10$)가 주어진다. 각 테스트 케이스는 $N$과 $K$가 적힌 줄로 시작한다. 다음 줄에는 길이 $N$의 문자열이 주어지며, $i$번째 문자는 $i$번째 소의 품종이다. G는 Guernsey, H는 Holstein을 뜻한다.

각 테스트 케이스마다 두 줄을 출력한다. 첫 줄에는 모든 소에게 먹이를 주는 데 필요한 풀밭의 최소 개수를 출력한다. 둘째 줄에는 길이 $N$의 문자열을 출력한다. $i$번째 문자는 위치 $i$에 풀밭이 없으면 '.', Guernsey용 풀밭이면 'G', Holstein용 풀밭이면 'H'이다. 최소 개수의 풀밭으로 모든 소에게 먹이를 주는 배치라면 어떤 것이든 허용된다.

최소 개수의 풀밭으로 조건을 만족하는 배치가 여러 개인 경우가 있다. 예를 들어 네 번째 테스트 케이스에서는 다음도 정답으로 인정된다.

.GH..

이 배치는 2번 위치에 Guernsey용 풀밭, 3번 위치에 Holstein용 풀밭을 둔다. 풀밭 수가 최적이며, 모든 소가 선호하는 풀밭에서 3칸 이내에 있다.