简单版本和困难版本之间的唯一区别是输入的大小。
给定一个字符串 $$$s$$$,由 $$$n$$$ 个字符组成,每个字符是“R”、“G”或“B”。
您还获得了一个整数 $$$k$$$。您的任务是更改初始字符串 $$$s$$$ 中的最小字符数,以便更改后将出现一个长度为 $$$k$$$ 的字符串,该字符串是 $$$s$$$ 的子字符串,也是无限字符串“RGBRGBRGB ...”的子字符串。
如果存在正整数 $$$i$$$,使得 $$$a_1 = b_i$$$、$$$a_2 = b_{i + 1}$$$、$$$a_3 = b_{i + 2}$$$、...、$$$a_{|a|} = b_{i,则字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串+ |一个| - 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$$$ 中更改的最小字符数,以便更改后 $$$s$$$ 中将有一个长度为 $$$k$$$ 的子字符串,它也是无限字符串“RGBRGBRGB ...”的子字符串。
示例
输入 #1
3 5 2 BGGGG 5 3 RBRGR 5 5 BBBRR
输出 #1
1 0 3
注意
在第一个示例中,您可以将第一个字符更改为“R”并获得子字符串“RG”,或者将第二个字符更改为“R”并获得“BR”,或者将第三个、第四个或第五个字符更改为“B”并获得“GB”。
在第二个示例中,子字符串是“BRG”。