The only difference between easy and hard versions is the size of the input.

You are given a string $s$ consisting of $n$ characters, each character is 'R', 'G' or 'B'.

You are also given an integer $k$. Your task is to change the minimum number of characters in the initial string $s$ so that after the changes there will be a string of length $k$ that is a substring of $s$, and is also a substring of the infinite string "RGBRGBRGB ...".

A string $a$ is a substring of string $b$ if there exists a positive integer $i$ such that $a_1 = b_i$, $a_2 = b_{i + 1}$, $a_3 = b_{i + 2}$, ..., $a_{|a|} = b_{i + |a| - 1}$. For example, strings "GBRG", "B", "BR" are substrings of the infinite string "RGBRGBRGB ..." while "GR", "RGR" and "GGG" are not.

You have to answer $q$ independent queries.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries. Then $q$ queries follow.

The first line of the query contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the length of the string $s$ and the length of the substring.

The second line of the query contains a string $s$ consisting of $n$ characters 'R', 'G' and 'B'.

It is guaranteed that the sum of $n$ over all queries does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each query print one integer — the minimum number of characters you need to change in the initial string $s$ so that after changing there will be a substring of length $k$ in $s$ that is also a substring of the infinite string "RGBRGBRGB ...".


-----Example-----
Input
3
5 2
BGGGG
5 3
RBRGR
5 5
BBBRR

Output
1
0
3



-----Note-----

In the first example, you can change the first character to 'R' and obtain the substring "RG", or change the second character to 'R' and obtain "BR", or change the third, fourth or fifth character to 'B' and obtain "GB".

In the second example, the substring is "BRG".

Difficulty: introductory

Starter code:

Solutions:
from sys import stdin
import math

rgb = 'RGB'

for query in range(int(stdin.readline())):
    n, k = list(map(int, stdin.readline().split()))
    s = stdin.readline()

    ans = math.inf
    for start in range(3):
        dp = [0 for i in range(n + 1)] 
        for i in range(n):
            cur = rgb[(start + i) % len(rgb)]
            dp[i + 1] = dp[i] + int(s[i] != cur)
        for i in range(n - k + 1):
            ans = min(ans, dp[i + k] - dp[i])
    print(ans)




from sys import stdin
from collections import deque
c=int(stdin.readline().strip())
for cas in range(c):
    n,m=list(map(int,stdin.readline().strip().split()))
    s=deque(stdin.readline().strip())
    arr=["R","G","B"]
    ans=n+3
    for k in range(1):

        for  i in range(3):
            x=i

            dp=[0 for i in range(n+1)]
            for j in range(n):

                if s[j]!=arr[x]:
                    dp[j+1]+=1
                dp[j+1]+=dp[j]
                if j+1>=m:

                    ans=min(ans,dp[j+1]-dp[j+1-m])
                x+=1
                x=x%3

    print(ans)
                
            
    
            
            
1


import sys
input = sys.stdin.readline

q=int(input())

for testcases in range(q):
    n,k=list(map(int,input().split()))
    S=list(input().strip())

    for i in range(n):
        if S[i]=="R":
            S[i]=0
        elif S[i]=="G":
            S[i]=1
        else:
            S[i]=2

    ANS=1<<50



    for mod in range(3):
        SUM=0
        for i in range(k):
            if S[i]%3!=(mod+i)%3:
                SUM+=1

        ANS=min(ANS,SUM)


        for i in range(k,n):
            if S[i-k]!=(mod+(i-k))%3:
                SUM-=1
            if S[i]!=(mod+i)%3:
                SUM+=1



            ANS=min(ANS,SUM)

    print(ANS)

        
                
        

    


import sys
input = sys.stdin.readline
q = int(input())
for i in range(q):
    n, k = map(int, input().split())
    s = input()
    R, G, B = 0, 0, 0
    ans = float('inf')
    for j in range(n):
        if j % 3 == 0:
            if s[j] == 'R':
                G += 1
                B += 1
            elif s[j] == 'G':
                R += 1
                B += 1
            else:
                R += 1
                G += 1
        elif j % 3 == 1:
            if s[j] == 'R':
                G += 1
                R += 1
            elif s[j] == 'G':
                G += 1
                B += 1
            else:
                R += 1
                B += 1
        else:
            if s[j] == 'R':
                R += 1
                B += 1
            elif s[j] == 'G':
                R += 1
                G += 1
            else:
                G += 1
                B += 1
        if j >= k - 1:
            ans = min(ans, R, G, B)
            if (j - k + 1) % 3 == 0:
                if s[j - k + 1] == 'R':
                    G -= 1
                    B -= 1
                elif s[j - k + 1] == 'G':
                    R -= 1
                    B -= 1
                else:
                    R -= 1
                    G -= 1
            elif (j - k + 1) % 3 == 1:
                if s[j - k + 1] == 'R':
                    G -= 1
                    R -= 1
                elif s[j - k + 1] == 'G':
                    G -= 1
                    B -= 1
                else:
                    R -= 1
                    B -= 1
            else:
                if s[j - k + 1] == 'R':
                    R -= 1
                    B -= 1
                elif s[j - k + 1] == 'G':
                    R -= 1
                    G -= 1
                else:
                    G -= 1
                    B -= 1

    print(ans)

import sys
input = sys.stdin.readline
Q = int(input())
D = {"R":0, "G":1, "B":2}
for _ in range(Q):
    N, K = list(map(int, input().split()))
    S = input()
    mi = K
    for i in range(3):
        d = 0
        for j in range(N):
            if D[S[j]] != (i+j) % 3:
                d += 1
            if j >= K and D[S[j-K]] != (i+j-K) % 3:
                d -= 1
            if j >= K-1:
                mi = min(mi, d)
    print(mi)


from sys import stdin,stdout
input=stdin.readline
for _ in range(int(input())):
    x=10**5
    n,k=list(map(int,input().split()))
    s=input()
    a=10**9
    ans=[[0]*n for i in range(3)]
    curr=['R','G','B']
    for l in range(3):
        z=l
        for j in range(n):
            if s[j]!=curr[z]:
                ans[l][j]=1
            z+=1
            z%=3
    for i in range(3):
        ans[i]=[0]+ans[i]
    for l in range(3):
        z=l
        for j in range(1,n+1):
            ans[l][j]+=ans[l][j-1]
    for l in range(3):
        for j in range(1,n-k+2):
            a=min(a,ans[l][j+k-1]-ans[l][j-1])
   # print(ans)
    print(a)


''' CODED WITH LOVE BY SATYAM KUMAR '''

from sys import stdin, stdout
import cProfile, math
from collections import Counter,defaultdict,deque
from bisect import bisect_left,bisect,bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
sys.setrecursionlimit(10**6) # max depth of recursion
threading.stack_size(2**27)  # new thread will get stack of such size
fac_warmup = False
printHeap = str()
memory_constrained = False
P = 10**9+7
import sys

class merge_find:
    def __init__(self,n):
        self.parent = list(range(n))
        self.size = [1]*n
        self.num_sets = n
        self.lista = [[_] for _ in range(n)]
    def find(self,a):
        to_update = []
        while a != self.parent[a]:
            to_update.append(a)
            a = self.parent[a]
        for b in to_update:
            self.parent[b] = a
        return self.parent[a]
    def merge(self,a,b):
        a = self.find(a)
        b = self.find(b)
        if a==b:
            return
        if self.size[a]<self.size[b]:
            a,b = b,a
        self.num_sets -= 1
        self.parent[b] = a
        self.size[a] += self.size[b]
        self.lista[a] += self.lista[b]
    def set_size(self, a):
        return self.size[self.find(a)]
    def __len__(self):
        return self.num_sets

def display(string_to_print):
    stdout.write(str(string_to_print) + "\n")

def primeFactors(n): #n**0.5 complex 
    factors = dict()
    for i in range(2,math.ceil(math.sqrt(n))+1):  
        while n % i== 0: 
            if i in factors:
                factors[i]+=1
            else: factors[i]=1
            n = n // i 
    if n>2:
        factors[n]=1
    return (factors)

def all_factors(n):    
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

def fibonacci_modP(n,MOD):
    if n<2: return 1
    #print (n,MOD)
    return (cached_fn(fibonacci_modP, (n+1)//2, MOD)*cached_fn(fibonacci_modP, n//2, MOD) + cached_fn(fibonacci_modP, (n-1) // 2, MOD)*cached_fn(fibonacci_modP, (n-2) // 2, MOD)) % MOD

def factorial_modP_Wilson(n , p): 
    if (p <= n): 
        return 0
    res = (p - 1) 
    for i in range (n + 1, p): 
        res = (res * cached_fn(InverseEuler,i, p)) % p 
    return res 

def binary(n,digits = 20):
    b = bin(n)[2:]
    b = '0'*(digits-len(b))+b
    return b

def isprime(n):
    """Returns True if n is prime."""
    if n < 4:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False
    i = 5
    w = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += w
        w = 6 - w
    return True

def generate_primes(n):
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * 2, n+1, p): 
                prime[i] = False
        p += 1
    return prime

factorial_modP = []
def warm_up_fac(MOD):
    nonlocal factorial_modP,fac_warmup
    if fac_warmup: return
    factorial_modP= [1 for _ in range(fac_warmup_size+1)]
    for i in range(2,fac_warmup_size):
        factorial_modP[i]= (factorial_modP[i-1]*i) % MOD
    fac_warmup = True

def InverseEuler(n,MOD):
    return pow(n,MOD-2,MOD)

def nCr(n, r, MOD):
    nonlocal fac_warmup,factorial_modP
    if not fac_warmup:
        warm_up_fac(MOD)
        fac_warmup = True
    return (factorial_modP[n]*((pow(factorial_modP[r], MOD-2, MOD) * pow(factorial_modP[n-r], MOD-2, MOD)) % MOD)) % MOD

def test_print(*args):
    if testingMode:
        print(args)

def display_list(list1, sep=" "):
    stdout.write(sep.join(map(str, list1)) + "\n")

def display_2D_list(li):
    for i in li:
        print(i)
def prefix_sum(li):
    sm = 0
    res = []
    for i in li:
        sm+=i
        res.append(sm)
    return res

def get_int():
    return int(stdin.readline().strip())

def get_tuple():
    return map(int, stdin.readline().split())

def get_list():
    return list(map(int, stdin.readline().split()))
import heapq,itertools
pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>' 
def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heapq.heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heapq.heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')
memory = dict()
def clear_cache():
    nonlocal memory
    memory = dict()
def cached_fn(fn, *args):
    nonlocal memory
    if args in memory:
        return memory[args]
    else:
        result = fn(*args)
        memory[args] = result
        return result

def ncr (n,r):
    return math.factorial(n)/(math.factorial(n-r)*math.factorial(r))
def binary_serach(i,li):
    #print("Search for ",i)
    fn = lambda x: li[x]-x//i
    x = -1
    b = len(li)
    while b>=1:
        #print(b,x)
        while b+x<len(li) and fn(b+x)>0: #Change this condition 2 to whatever you like
            x+=b
        b=b//2
    return x

# -------------------------------------------------------------- MAIN PROGRAM
TestCases = True
testingMode = False
fac_warmup_size = 10**5+100
optimiseForReccursion = False #Can not be used clubbed with TestCases # WHen using recursive functions, use Python 3
from math import factorial

def main():
    n, k = get_tuple()
    st = stdin.readline()
    li = ['R','G','B']

    for offset in range(3):
        cnt = 0
        for i in range(k):
            if st[i]!=li[(i+offset)%3]:
                cnt+=1
        if offset==0: min_cnt = cnt
        min_cnt = min(min_cnt, cnt)
        for i in range(k,n):
            if st[i-k]!=li[(i-k+offset)%3]:
                cnt-=1
            if st[i]!=li[(i+offset)%3]:
                cnt+=1
            min_cnt = min(min_cnt, cnt)
    print(min_cnt)






# --------------------------------------------------------------------- END=


if TestCases: 
    for i in range(get_int()): 
        cProfile.run('main()') if testingMode else main() 
else: (cProfile.run('main()') if testingMode else main()) if not optimiseForReccursion else threading.Thread(target=main).start()

def main():
    q = int(input())
    ans = []
    for i in range(q):
        n, k = map(int, input().split())
        s = input()
        min_ans = 10 ** 9
        pr1 = [0]
        pr2 = [0]
        pr3 = [0]        
        for i in range(n):
            count1 = 0
            count2 = 0
            count3 = 0
            if i % 3 == 0:
                if s[i] != "R":
                    count1 += 1
                if s[i] != "G":
                    count2 += 1
                if s[i] != "B":
                    count3 += 1
            if i % 3 == 1:
                if s[i] != "G":
                    count1 += 1
                if s[i] != "B":
                    count2 += 1
                if s[i] != "R":
                    count3 += 1 
            if i % 3 == 2:
                if s[i] != "B":
                    count1 += 1
                if s[i] != "R":
                    count2 += 1
                if s[i] != "G":
                    count3 += 1
            pr1.append(pr1[-1] + count1)
            pr2.append(pr2[-1] + count2)
            pr3.append(pr3[-1] + count3)
            j = i + 1
            if j >= k:
                count1 = pr1[j] - pr1[j - k]
                count2 = pr2[j] - pr2[j - k]
                count3 = pr3[j] - pr3[j - k]
                min_ans = min(min_ans, count1, count2, count3)     
        ans.append(min_ans)
    print(*ans, sep="\n")

main()

import sys
input = lambda: sys.stdin.readline().strip()

nxt = {'R':'G', 'G':'B', 'B':'R'}

T = int(input())
for _ in range(T):
    n, k = list(map(int, input().split()))
    s = input()
    res = []
    for start in ['R', 'G', 'B']:
        mis = []
        cur = start
        for j in range(k):
            if s[j]!=cur: mis.append(1)
            else: mis.append(0)
            cur = nxt[cur]
        res.append(sum(mis))
        for j in range(k, n):
            res.append(res[-1]+int(s[j]!=cur)-mis[j-k])
            if s[j]!=cur: mis.append(1)
            else: mis.append(0)
            cur = nxt[cur]
    print(min(res))


import sys
input = sys.stdin.readline
q = int( input() )
rgb = "RGB"
for _ in range( q ):
    n, k = list(map( int, input().split() ))
    s = input()
    ans = n
    for i in range( 3 ):
        r = [ 0 ]
        l = i
        for c in s:
            r.append( r[ -1 ] + ( 1 if c != rgb[ l ] else 0 ) )
            l = ( l + 1 ) % 3
            if len( r ) > k:
                ans = min( ans, r[ -1 ] - r[ len( r ) - 1 - k ] )
    print( ans )


import sys

t=int(sys.stdin.readline())
x='RGB'
y='GBR'
z='BRG'
# x='RGB'
for i in range(t):
    n,k=list(map(int,sys.stdin.readline().strip().split()))
    a=sys.stdin.readline().strip()
    xk=x
    yk=y
    zk=z
   
    op=2001
    
    xd=[]
    yd=[]
    zd=[]
    xdc=0
    ydc=0
    zdc=0
    b=a
    for j in range(k):
        if(b[j]!=xk[j%3]):
            xd.append(1)
            xdc+=1
        else:
            xd.append(0)
            
        if(b[j]!=yk[j%3]):
            yd.append(1)
            ydc+=1
        else:
            yd.append(0)
            
        if(b[j]!=zk[j%3]):
            zdc+=1
            zd.append(1)
        else:
            zd.append(0)
    op=min(xdc,ydc,zdc)
    
    for j in range(k,n):
        # print(b,len(b),j,xk)
        if(b[j]!=xk[j%3]):
            xd.append(1)
            xdc+=1
        else:
            xd.append(0)
            
        if(b[j]!=yk[j%3]):
            yd.append(1)
            ydc+=1
        else:
            yd.append(0)
            
        if(b[j]!=zk[j%3]):
            zdc+=1
            zd.append(1)
        else:
            zd.append(0)
        # print("here")
        xdc-=xd[j-k]
        ydc-=yd[j-k]
        zdc-=zd[j-k]
        op=min(op,xdc,ydc,zdc)
    print(op)
    
#oh , had been testing with other test case, first had set only x, but then added back y and z :P


import sys
for _ in range(int(sys.stdin.readline())):
    n, k = [int(i) for i in sys.stdin.readline().split()]
    word = sys.stdin.readline().strip()
    ans = 0
    for col in ["RGB", "GBR", "BRG"]:
        cnt = 0
        for i in range(k):
            if word[i] == col[i%3]:
                cnt += 1
        mx = cnt
        for i in range(n-k):
            if word[i+k] == col[(i+k)%3]:
                cnt += 1
            if word[i] == col[i%3]:
                cnt -= 1
            if cnt > mx:
                mx = cnt
        ans = max(ans, mx)
    sys.stdout.write(str(k - ans) + "\n")



a = int(input())
ot = ''
for i in range(a):
    b, c = list(map(int,input().split()))
    s = input()
    pref = [0] * (b + 1)
    pref1 = [0] * (b + 1)
    pref2 = [0] * (b + 1)
    n = 'RGB'
    n1 = 'GBR'
    n2 = 'BRG'
    for j in range(b):
        pref[j + 1] = pref[j]
        if s[j] != n[j % 3]:
            pref[j + 1] += 1
        pref1[j + 1] = pref1[j]
        if s[j] != n1[j % 3]:
            pref1[j + 1] += 1
        pref2[j + 1] = pref2[j]
        if s[j] != n2[j % 3]:
            pref2[j + 1] += 1
    mi = 1000000000
    #print(*pref)
    #print(*pref1)
    #print(*pref2)
    for j in range(c, b + 1):
        mi = min(pref[j] - pref[j - c], pref1[j] - pref1[j - c], pref2[j] - pref2[j - c], mi)
        #print(mi, j)
    mi = min(pref[-1], pref1[-1], pref2[-1],  mi)
    ot += str(mi) + '\n'
print(ot)


from heapq import heappush, heappop
from collections import deque, Counter, defaultdict
import itertools
import sys
#import bisect
sys.setrecursionlimit(10**6)
def MI():
    return list(map(int,input().split()))
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['YES','NO']
input=sys.stdin.readline
 
q=I()
for _ in range(q):
    
    n,k=LI()
    ans=k
    s=list(input())
    l='RGB'
    c=[[0],[0],[0]]
    
    for i in range(n):
        for j in range(3):
            if s[i]!=l[(i+j)%3]:
                c[j].append(c[j][-1]+1)
            else:
                c[j].append(c[j][-1])
    
    #print(c)
    for i in range(n-k+1):
        for j in range(3):
            ans=min(c[j][i+k]-c[j][i],ans)
    print(ans)


from sys import stdin

input = stdin.readline

q = int(input())

for ppppp in range(q):
    [n, k] = [int(item) for item in input().split(' ')]
    x = input()

    inf_seq = 'RGB'
    ptr = 0

    weights = []
    cost = [0, 0, 0]
    for i in range(k):
        dd = [0, 0, 0]
        for d in range(3):
            if x[i] != inf_seq[(i + d) % 3]:
                dd[d] = 1
                cost[d] += 1
        weights.append(dd)

    min_changes = min(cost)

    for i in range(k, n):
        dd = [0, 0, 0]
        for d in range(3):
            # remove previous cost
            cost[d] -= weights[i - k][d]

            if x[i] != inf_seq[(i + d) % 3]:
                dd[d] = 1
                cost[d] += 1
        weights.append(dd)
        min_changes = min(min_changes, min(cost))

    print(min_changes)


# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
from sys import stdin, stdout
import collections

Q = int(input())
ans = [0]*Q
#s = input()
#N = len(s)
#arr = [int(x) for x in stdin.readline().split()]
for q in range(Q):

    N,K = [int(x) for x in stdin.readline().split()]
    s = input()
    res = N+1

    if N==1 or K==1:
        #print(0)
        ans[q] = 0
        continue

    prefix = [0]*(N+1)

    for k in range(3):
        if k==0:
            RGB = 'RGB'
        if k==1:
            RGB = 'GBR'
        if k==2:
            RGB = 'BRG'

        ssum = 0
        for i in range(N):
            letter = RGB[i%3]
            if s[i]!=letter:
                ssum += 1
            prefix[i+1] = ssum
            if i>=K-1:
                res = min(res,prefix[i+1] - prefix[i+1-K])

    ans[q] = res

print(*ans,sep='\n')

import sys
input=sys.stdin.readline
q=int(input())
for i in range(q):
    n,k=map(int,input().split())
    s=input()[:n]
    if k==1:
        print(0)
        continue
    rgb=[0,0,0]
    a=1
    for j,c in enumerate(s):
        if c=="R":
            rgb[j%3]+=1
        elif c=="G":
            rgb[(j-1)%3]+=1
        else:
            rgb[(j-2)%3]+=1
        if j+1>=k:
            a=max(a,max(rgb))
            t=s[j-k+1]
            if t=="R":
                rgb[(j-k+1)%3]-=1
            elif t=="G":
                rgb[(j-k)%3]-=1
            else:
                rgb[(j-k-1)%3]-=1
            if a==k:
                print(0)
                break
    else:
        print(k-a)

# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
from sys import stdin, stdout
import collections

Q = int(input())
ans = [0]*Q
#s = input()
#N = len(s)
#arr = [int(x) for x in stdin.readline().split()]
for q in range(Q):

    N,K = [int(x) for x in stdin.readline().split()]
    s = input()
    res = N+1

    if N==1 or K==1:
        #print(0)
        ans[q] = 0
        continue

    prefix = [0]*(N+1)

    for k in range(3):
        if k==0:
            RGB = 'RGB'
        if k==1:
            RGB = 'GBR'
        if k==2:
            RGB = 'BRG'

        ssum = 0
        for i in range(N):
            letter = RGB[i%3]
            if s[i]!=letter:
                ssum += 1
            prefix[i+1] = ssum
            if i>=K-1:
                res = min(res,prefix[i+1] - prefix[i+1-K])

    ans[q] = res

print(*ans,sep='\n')

def int_list():
    return  [int(c) for c in input().split()]

def int1():
    return int(input())

def str_list():
    return [c for c in input().split()]

def str1():
    return input()

# start

s1 = ("RGB" * 66667)[:-1]
s2 = ("GBR" * 66667)[:-1]
s3 = ("BRG" * 66667)[:-1]

q = int1()
res = []

for j in range(q):
    n, k = int_list()
    s = str1()

    c1 = []
    c2 = []
    c3 = []

    for i in range(n):
        if s[i] != s1[i]:
            c1.append(1)
        else:
            c1.append(0)
        if s[i] != s2[i]:
            c2.append(1)
        else:
            c2.append(0)
        if s[i] != s3[i]:
            c3.append(1)
        else:
            c3.append(0)

    min1 = sum(c1[:k])
    min2 = sum(c2[:k])
    min3 = sum(c3[:k])

    cost1 = min1
    cost2 = min2
    cost3 = min3

    for i in range(k, n):
        cost1 += (c1[i] - c1[i-k])
        cost2 += (c2[i] - c2[i-k])
        cost3 += (c3[i] - c3[i-k])

        min1 = cost1 if cost1 < min1 else min1
        min2 = cost2 if cost2 < min2 else min2
        min3 = cost3 if cost3 < min3 else min3

    res.append(min(min1, min2, min3))

for result in res:
    print(result)


q=int(input())
f=[]
for i in range(q):
    n,k=map(int,input().split())
    s=input()
    mi=0
    num=[0,0,0]
    for i in range(n):
        if i%3==0:
            if s[i]=='R':
                num[0]+=1
            elif s[i]=='G':
                num[1]+=1
            else:
                num[2]+=1
        elif i%3==1:
            if s[i]=='G':
                num[0]+=1
            elif s[i]=='B':
                num[1]+=1
            else:
                num[2]+=1
        else:
            if s[i]=='B':
                num[0]+=1
            elif s[i]=='R':
                num[1]+=1
            else:
                num[2]+=1
        if i>=k:
            if (i-k)%3==0:
                if s[i-k]=='R':
                    num[0]-=1
                elif s[i-k]=='G':
                    num[1]-=1
                else:
                    num[2]-=1
            elif (i-k)%3==1:
                if s[i-k]=='G':
                    num[0]-=1
                elif s[i-k]=='B':
                    num[1]-=1
                else:
                    num[2]-=1
            else:
                if s[i-k]=='B':
                    num[0]-=1
                elif s[i-k]=='R':
                    num[1]-=1
                else:
                    num[2]-=1
        e=max(num)
        if mi<e:
            mi=e
    f+=[k-mi]
for i in f:
    print(i)

import sys
 
t = int(input())
for _ in range(t):
    n, k = list(map(int, sys.stdin.readline().split()))
    s = sys.stdin.readline()
    d = {}
    d['R'] = [0,0,0]
    d['G'] = [0,0,0]
    d['B'] = [0,0,0]
    res = 0
    for i in range(k):
        d[s[i]][i%3] += 1
    res = max(d['R'][0] + d['G'][1] + d['B'][2], d['R'][1] + d['G'][2] + d['B'][0], d['R'][2] + d['G'][0] + d['B'][1])
    for i in range(k, n):
        d[s[i]][i%3] += 1
        d[s[i-k]][(i-k)%3] -= 1
        res = max(res, d['R'][0] + d['G'][1] + d['B'][2], d['R'][1] + d['G'][2] + d['B'][0], d['R'][2] + d['G'][0] + d['B'][1])
        if res >= k:
            break
    print(k-res)
        



from sys import stdin
input=stdin.readline
for _ in range(int(input())):
    n,k=map(int,input().split())
    s=list(input())
    ans=10**9
    a=['R','G','B']
    for l in range(3):
        x=l
        dp=[0]*(n+1)
        cnt=10**9
        for i in range(n):
            if s[i]!=a[x]:
                dp[i+1]=dp[i]+1
            else: dp[i+1]=dp[i]
            x=(x+1)%3
        for i in range(1,n-k+2):
            cnt=min(cnt,dp[i+k-1]-dp[i-1])
        ans=min(cnt,ans)
    print(ans)

import sys
def main():
    def diff(s,l):
        ret1 = [0 for k in range(len(s))]
        for k in range(len(s)):
            if k%3 == 0 and s[k] != "R":
                ret1[k] = 1
            if k%3 == 1 and s[k] != "G":
                ret1[k] = 1
            if k%3 == 2 and s[k] != "B":
                ret1[k] = 1
        ret2 = [0] * len(s)
        for k in range(len(s)):
            if k%3 == 0 and s[k] != "G":
                ret2[k] = 1
            if k%3 == 1 and s[k] != "B":
                ret2[k] = 1
            if k%3 == 2 and s[k] != "R":
                ret2[k] = 1
        ret3 = [0] * len(s)
        for k in range(len(s)):
            if k%3 == 0 and s[k] != "B":
                ret3[k] = 1
            if k%3 == 1 and s[k] != "R":
                ret3[k] = 1
            if k%3 == 2 and s[k] != "G":
                ret3[k] = 1
        s1 = [0] * (len(s)+1)
        s2 = [0] * (len(s)+1)
        s3 = [0] * (len(s)+1)
        for k in range(1,n+1):
            s1[k] = s1[k-1] + ret1[k-1]
            s2[k] = s2[k-1] + ret2[k-1]
            s3[k] = s3[k-1] + ret3[k-1]
        ans = 1000000
        for k in range(len(s)-l):
            ans = min(ans,s1[k+l]-s1[k],s2[k+l]-s2[k],s3[k+l]-s3[k])
        return ans
    input = sys.stdin.readline
    q = int(input())
    for query in range(q):
        n, k = list(map(int,input().split()))
        s = input()
        print(diff(s,k))
def __starting_point():
    main()

__starting_point()

import sys
for _ in range(int(sys.stdin.readline())):
    n, k = [int(i) for i in sys.stdin.readline().split()]
    word = sys.stdin.readline().strip()
    ans = 0
    for col in ["RGB", "GBR", "BRG"]:
        cnt = 0
        for i in range(k):
            if word[i] == col[i%3]:
                cnt += 1
        mx = cnt
        for i in range(n-k):
            if word[i+k] == col[(i+k)%3]:
                cnt += 1
            if word[i] == col[i%3]:
                cnt -= 1
            if cnt > mx:
                mx = cnt
        ans = max(ans, mx)
    sys.stdout.write(str(k - ans) + "\n")