У Фермера Джона имеется \(N\) (\(1 \le {N} \le {10^5}\)) коров, каждая из которых имеет
породу или Guernsey(G) или Holstein(H). Они выстроились в ряд заняв позиции \(1\dots N\).
Поскольку все коровы голодные, ФД решил выложить пакты с травой в некоторых
позициях \(1\dots N\). Коровы разных пород едят разные типы травы. Каждый пакет
травы должен содержать траву только одного типа (для G или для H). Он не может
разместить пакеты с разной травой в одной и той же позиции. Каждый пакет травы
может накормить неограниченное количество коров соответствующего типа.
Каждая корова готова пройти не более \(K\) (\(0 \le {K} \le N-1\)) позиций
чтобы добраться до пакета с травой. Определите минимальное количество пакетов
с травой, необходимое чтобы накормить всех коров. Любая конфигурация, удовлетворяющая
указанным выше ограничениям, будет рассматриваться как корректная.
ФОРМАТ ВВОДА (с клавитатуры / stdin):
Каждый тест состоит из
\(T\) подтестов, описывающих расположение коров.
Первая строка сдержит
\(T\) (
\(1 \le T \le 10\)). Далее следует
\(T\) подтестов.
Каждый подтест начинается со строки содержащей \(N\) и \(K\).
Следующая строка содержит строку длины \(N\), в которой каждый символ
обозначает породу коровы на позиции \(i\) (G или H).
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого из \(T\) подтестов выведите две строки.
В первой строке выведите минимальное количество пакетов с травой, которые требуются.
Во второй строке нужно вывести строку из \(N\) символов, которая описывает Ваше решение.
\(i\)-ый символ этой строки указывает что нужно разместить в позиции \(i\):
'.' - ничего
'G' - пакет с травой типа G
'H' - пакет с травой типа H
Любая корректная конфигурация будет принята.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|