D2. Подстрока RGB (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие между простой и сложной версиями — размер входных данных.

Вам задана строка $$$s$$$, состоящая из $$$n$$$ символов, каждый символ равен 'R', 'G' или 'B'.

Вам также задано целое число $$$k$$$. Ваша задача — изменить минимальное количество символов в изначальной строке $$$s$$$ таким образом, что после этих изменений найдется строка длины $$$k$$$ такая, что она является и подстрокой $$$s$$$, и подстрокой бесконечной строки «RGBRGBRGB ...».

Строка $$$a$$$ называется подстрокой $$$b$$$, если существует положительное целое число $$$i$$$, что $$$a_1 = b_i$$$, $$$a_2 = b_{i + 1}$$$, $$$a_3 = b_{i + 2}$$$, ..., $$$a_{|a|} = b_{i + |a| - 1}$$$. Например, строки «GBRG», «B», «BR» являются подстроками бесконечной строки «RGBRGBRGB ...»,а строки «GR», «RGR» и «GGG» — нет.

Вам необходимо ответить на $$$q$$$ независимых запросов.

Входные данные

Первая строка входных данных содержит одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов. Затем следуют $$$q$$$ запросов.

Первая строка запроса содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — длину строки $$$s$$$ и длину подстроки.

Вторая строка запроса содержит строку $$$s$$$, состоящую из $$$n$$$ символов 'R', 'G' и 'B'.

Гарантируется, что сумма $$$n$$$ по всем запросам не превосходит $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

Выходные данные

На каждый запрос выведите одно число — минимальное количество символов, которое вам необходимо изменить в изначальной строке $$$s$$$, чтобы после изменений нашлась такая подстрока длины $$$k$$$ в $$$s$$$, что она также является подстрокой бесконечной строки «RGBRGBRGB ...».

Пример
Входные данные
3
5 2
BGGGG
5 3
RBRGR
5 5
BBBRR
Выходные данные
1
0
3
Примечание

В первом тестовом примере вы можете изменить первый символ на 'R' и получить подстроку «RG», или изменить второй символ на 'R' и получить подстроку «BR», или изменить третий, четвертый или пятый символ на 'B' и получить «GB».

Во втором тестовом примере подстрока равна «BRG».