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

Вам задана строка $$$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$$$ независимых запросов.