Единственное отличие между простой и сложной версиями — размер входных данных.
Вам задана строка \(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\) независимых запросов.
Выходные данные
На каждый запрос выведите одно число — минимальное количество символов, которое вам необходимо изменить в изначальной строке \(s\), чтобы после изменений нашлась такая подстрока длины \(k\) в \(s\), что она также является подстрокой бесконечной строки «RGBRGBRGB ...».
Примечание
В первом тестовом примере вы можете изменить первый символ на 'R' и получить подстроку «RG», или изменить второй символ на 'R' и получить подстроку «BR», или изменить третий, четвертый или пятый символ на 'B' и получить «GB».
Во втором тестовом примере подстрока равна «BRG».