You have a garland consisting of $n$ lamps. Each lamp is colored red, green or blue. The color of the $i$-th lamp is $s_i$ ('R', 'G' and 'B' — colors of lamps in the garland).

You have to recolor some lamps in this garland (recoloring a lamp means changing its initial color to another) in such a way that the obtained garland is diverse.

A garland is called diverse if any two adjacent (consecutive) lamps (i. e. such lamps that the distance between their positions is $1$) have distinct colors.

In other words, if the obtained garland is $t$ then for each $i$ from $1$ to $n-1$ the condition $t_i \ne t_{i + 1}$ should be satisfied.

Among all ways to recolor the initial garland to make it diverse you have to choose one with the minimum number of recolored lamps. If there are multiple optimal solutions, print any of them.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of lamps.

The second line of the input contains the string $s$ consisting of $n$ characters 'R', 'G' and 'B' — colors of lamps in the garland.


-----Output-----

In the first line of the output print one integer $r$ — the minimum number of recolors needed to obtain a diverse garland from the given one.

In the second line of the output print one string $t$ of length $n$ — a diverse garland obtained from the initial one with minimum number of recolors. If there are multiple optimal solutions, print any of them.


-----Examples-----
Input
9
RBGRRBRGG

Output
2
RBGRGBRGR

Input
8
BBBGBRRR

Output
2
BRBGBRGR

Input
13
BBRRRRGGGGGRR

Output
6
BGRBRBGBGBGRG

Difficulty: introductory

Starter code:

Solutions:
def deal(a,b,c='0'):
    if(c=='0' or a==c):
        if(a=='R'):
            return 'B'
        if(a=='B'):
            return 'R'
        if(a=='G'):
            return 'B'
    if(a=='R' and c=='B'):
        b = 'G'
    if (a == 'R' and c == 'G'):
        b = 'B'
    if (a == 'B' and c == 'R'):
        b = 'G'
    if (a == 'B' and c == 'G'):
        b = 'R'
    if (a == 'G' and c == 'B'):
        b = 'R'
    if (a == 'G' and c == 'R'):
        b = 'B'
    return b
n = int(input())
ss = input()
s = list(ss)
answer = [s[0]]
number = 0
for i in range(0,n-1):
    ans = ""
    if (s[i]==s[i+1]):
        number += 1
        if(i==n-2):
            ans = deal(s[i],s[i+1])
        else:
            ans = deal(s[i],s[i+1],s[i+2])
        s[i+1] = ans
        answer.append(ans)
    else:
        answer.append(s[i+1])
s = "".join(answer)
print(number)
print(s)

input()
garor = list(input())
gar = garor.copy()
for i in range(1, len(gar)):
	if(gar[i]==gar[i-1]):
		options = ['R', 'G', 'B']
		options.remove(gar[i-1])
		if(i<len(gar)-1 and gar[i+1] in options):
			options.remove(gar[i+1])
		gar[i] = options[0]
count = 0
for i in range(0, len(gar)):
	if(gar[i]!=garor[i]):
		count = count +1
print(count)
str1 = ''.join(gar)
print(str1)



n = int(input())
si = input()
s = []
for i in si:
    s.append(i)

dic = {0:'R',1:'G',2:'B'}
dic2 = {'R':0,'G':1,'B':2}
c = 0
# print(s)
for i in range(1,len(s)):
    if i==(len(s)-1):
        if s[i] == s[i - 1]:
            s[i] = dic[(dic2[s[i]] + 1) % 3]
            c += 1
    else:
        if s[i]==s[i-1]:
            if s[i+1]==s[i-1]:
                s[i] = dic[(dic2[s[i]]+1)%3]
                c+=1
            else:
                temp = [False]*3
                temp[dic2[s[i - 1]]] = True
                temp[dic2[s[i + 1]]] = True
                for j in range(3):
                    if not temp[j]:
                        s[i]=dic[j]
                        c+=1
print(c)
for i in s:
    print(i,end='')



n = int(input())

s = [i for i in input()]

T = ['R','G','B']

add = 0

for i in range(n-1):
    if s[i] == s[i+1]:
        add += 1
        if i+2 < n:
            for j in T:
                if (j != s[i]) and (j !=s[i+2]):
                    s[i+1] = j
                    break
        else:
            for j in T:
                if (j != s[i]):
                    s[i+1] = j
                    break
print(add)
print(''.join(s))


n = int(input())
s = input()
s = [i for i in s]
ans = 0
e = ["R","G","B"]
for i in range(1,n):
    if s[i] == s[i-1]:
        ans += 1
        dame = set()
        dame.add(e.index(s[i-1]))
        if i != n-1:
            dame.add(e.index(s[i+1]))
        for j in range(3):
            if j in dame:
                continue
            else:
                s[i] = e[j]
                break
print(ans)
print("".join(s))

#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        #print(*args, **kwargs, file=sys.stderr)
        # in python 3.4 **kwargs is invalid???
        print(*args,  file=sys.stderr)
    dprint('debug mode')
except Exception:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    try:
        f = open('input'+ str(inId) + '.txt', 'r')
        sys.stdin = f #标准输出重定向至文件
    except Exception:
        dprint('invalid input file')
if outId>0:
    dprint('use output', outId)
    try:
        f = open('stdout'+ str(outId) + '.txt', 'w')
        sys.stdout = f #标准输出重定向至文件
    except Exception:
        dprint('invalid output file')
        
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
N, = getIntList()
#print(N)
s = input()
zs = list(s)
g = 'RGB'
r = 0
for i in range(1,N):
    if zs[i] == zs[i-1]:
        r+=1
        for x in g:
            if x == zs[i-1]: continue
            if i<N-1 and x == zs[i+1] : continue
            zs[i] = x
            break
print(r)
print(''.join(zs))







n = int(input())
s = '!' + input().strip()

dp = [[10 ** 6] * (n + 1) for i in range(3)]
pr = [[None] * (n + 1) for i in range(3)]
dp[0][0] = dp[1][0] = dp[2][0] = 0
for i in range(1, n + 1):
    for c in range(3):
        op1 = dp[(c + 1) % 3][i - 1]
        op2 = dp[(c + 2) % 3][i - 1]
        pr[c][i] = (c + 1) % 3 if op1 < op2 else (c + 2) % 3
        dp[c][i] = min(op1, op2) + ('RGB'.index(s[i]) != c)

ans = []
end = [dp[0][n], dp[1][n], dp[2][n]]
c = end.index(min(end))
for i in range(n, 0, -1):
    ans.append(c)
    c = pr[c][i]

print(min(end))
print(''.join('RGB'[c] for c in ans[::-1]))

n=int(input())
s=input()
lens=len(s)
dp=[[0]*5 for _ in range(lens+5)]
parent=[[0]*5 for _ in range(lens+5)]
R,G,B=1,2,3
sss="0RGB"

dp[0][R]=dp[0][G]=dp[0][B]=1
if s[0]=="R": dp[0][R]=0
if s[0]=="G": dp[0][G]=0
if s[0]=="B": dp[0][B]=0

for i in range(1,lens):
    dp[i][R]=min(dp[i-1][G],dp[i-1][B])+1
    if dp[i][R]==dp[i-1][G]+1:
        parent[i][R]=G
    else:
        parent[i][R]=B
    
    dp[i][G]=min(dp[i-1][R],dp[i-1][B])+1
    if dp[i][G]==dp[i-1][R]+1:
        parent[i][G]=R
    else:
        parent[i][G]=B

    dp[i][B]=min(dp[i-1][G],dp[i-1][R])+1
    if dp[i][B]==dp[i-1][G]+1:
        parent[i][B]=G
    else:
        parent[i][B]=R

    if s[i]=="R": dp[i][R]-=1
    elif s[i]=="G": dp[i][G]-=1
    elif s[i]=="B": dp[i][B]-=1

ans=min(dp[lens-1][R],dp[lens-1][G],dp[lens-1][B])
print(min(dp[lens-1][R],dp[lens-1][G],dp[lens-1][B]))

ans2=[0]*lens
if ans==dp[lens-1][R]:
    i=lens-1
    pp=R
    while i>=0:
        ans2[i]=sss[pp]
        pp=parent[i][pp]
        i-=1
elif ans==dp[lens-1][G]:
    i=lens-1
    pp=G
    while i>=0:
        ans2[i]=sss[pp]
        pp=parent[i][pp]
        i-=1
else:
    i=lens-1
    pp=B
    while i>=0:
        ans2[i]=sss[pp]
        pp=parent[i][pp]
        i-=1

print("".join(ans2))

import itertools
n = int(input())
s = list(input())
count = 0
values = {(l, r): next(iter(set("RGB") - {l, r})) for l, r in itertools.product("RGB", repeat=2)}
ranges = []
start = None
for i in range(1, n):
    if s[i - 1] == s[i]:
        if start is None:
            start = i - 1
    elif start is not None:
        ranges.append((start, i))
        start = None
if start is not None:
    ranges.append((start, n))

for r in ranges:
    for i in range(r[0] + 1, r[1], 2):
        l = s[i - 1]
        r = s[(i + 1) % n]
        s[i] = values[l, r]
        count += 1

print(count)
print("".join(s))


n = int(input())
s = input()
s = list(s)
if len(s) <= 2 and len(set(s)) > 1:
    print(0)
    print(''.join(s))
elif len(s) == 2:
    print(1)
    bam = 'RGB'
    print(s[0]+bam[(bam.index(s[0])+1)%3])
else:
    perekras = 0
    for t in range(1, len(s) - 1):
        if s[t-1] == s[t] and s[t] == s[t+1]:
            z = {'R', 'G', 'B'}
            perekras += 1
            z.discard(s[t-1])
            z.discard(s[t+1])
            s[t] = z.pop()
    for t in range(1, len(s) - 1):
        if s[t-1] == s[t] or s[t] == s[t+1]:
            z = {'R', 'G', 'B'}
            perekras += 1
            z.discard(s[t-1])
            z.discard(s[t+1])
            s[t] = z.pop()
    print(perekras)
    print(''.join(s))


def main():
    n = int(input())

    clone = set(["R","G","B"])

    lamps = [i for i in input()]
    c=0
    for i in range(len(lamps)-1):
        if lamps[i] == lamps[i+1] and i!=len(lamps)-2:
            t = clone - set([lamps[i],lamps[i+2]])
            lamps[i+1] = t.pop()
            c+=1
        if lamps[i] == lamps[i+1] and i==len(lamps)-2:
            t = clone - set([lamps[i]])
            lamps[i+1] = t.pop()
            c+=1

    print(c)
    print("".join(lamps))











main()

n = int(input())
a = input()
z = [a[0]]
s = ['R', 'B', 'G']
count = 0
for i in range(1, n):
    if a[i]!=z[-1]:
        z.append(a[i])
    else:
        for j in s:
            if i+1 < n:
                if j != a[i+1] and j != a[i]:
                    z.append(j)
                    count+=1
                    break
            else:
                if j != a[i]:
                    z.append(j)
                    count+=1
                    break
print(count)
print(''.join(z))

import sys

n = int(input())
lamps = input()

if len(lamps) == 1:
    print(0)
    print(lamps)
    return

def other(c1, c2='R'):
    if 'G' != c1 and 'G' != c2:
        return 'G'
    elif 'R' != c1 and 'R' != c2:
        return 'R'
    else:
        return 'B'

newlamps = list(lamps)
i = 1
recolors = 0
while i < n-1:
    if newlamps[i] == newlamps[i-1]:
        recolors += 1
        newlamps[i] = other(newlamps[i-1], newlamps[i+1])
    i += 1

if newlamps[-1] == newlamps[-2]:
    newlamps[-1] = other(newlamps[-2])
    recolors += 1

print(recolors)
print(''.join(newlamps))



n = int(input())
g = list(input())
cost = 0

for i in range(1, n):
    if g[i] == g[i-1]:
        cost += 1
        if i == n - 1 or g[i] == g[i+1]:
            if g[i] == 'R': g[i] = 'G'
            elif g[i] == 'G': g[i] = 'B'
            else: g[i] = 'R'
        else:
            if g[i] == 'R' and g[i+1] == 'G':
                g[i] = 'B'
            elif g[i] == 'R' and g[i+1] == 'B':
                g[i] = 'G'
            elif g[i] == 'G' and g[i+1] == 'R':
                g[i] = 'B'
            elif g[i] == 'G' and g[i+1] == 'B':
                g[i] = 'R'
            elif g[i] == 'B' and g[i+1] == 'R':
                g[i] = 'G'
            else:
                g[i] = 'R'

print(cost)
print(''.join(g))


def div_process(s, c):
  sl=list(s)
  for i in range(1, len(sl), 2):
    sl[i]=c
  return "".join(sl)

li=0
ct=0
input();i_s=input()
sp_l=[]
for i in range(1, len(i_s)):
  if not i_s[i]==i_s[i-1]:
    sp_l.append(i_s[li:i])
    li=i
sp_l.append(i_s[li:])

for i in range(len(sp_l)-1):
  sp_l[i]=div_process(sp_l[i], list({'R', 'G', 'B'}-{sp_l[i][0], sp_l[i+1][0]})[0])
sp_l[-1]=div_process(sp_l[-1], list({'R', 'G', 'B'}-{sp_l[-1][0]})[0])

print(sum([int(len(x)/2) for x in sp_l]))
print(''.join(sp_l))


n = int(input())
s = list(input())
cur = 'X'
start, end = 0, 0
i = 0
ans = 0
while i < n:
	if s[i] != cur:
		cur = s[i]
		start = i
		while i < n and s[i] == cur:
			i += 1
		if i == n:
			for ch in 'RBG':
				if ch != s[start]:
					use = ch
					break
		else:
			for ch in 'RBG':
				if ch != s[start] and ch != s[i]:
					use = ch
					break
		end = i - 1
		for j in range(start, end + 1):
			if (j - start) % 2:
				s[j] = use
				ans += 1
print(ans)
print(''.join(s))




import sys
input = sys.stdin.readline

n=int(input())
S=list(input())
ANS=0
LIST=["R","G","B"]
for i in range(1,n):
    
    if S[i]==S[i-1]:
        if i<n-1:
            for l in LIST:            
                if S[i-1]!=l and S[i+1]!=l:
                    ANS+=1
                    S[i]=l
                    break

        else:
            for l in LIST:
                if S[i-1]!=l:
                    ANS+=1
                    S[i]=l
                    break

print(ANS)
print("".join(S))
    




n=int(input())
f=["R","G","B"]
s=list(input())
i=1
x=0
while i<len(s)-1:
    if s[i]==s[i-1]:
        h=f[:]
        h.remove(s[i-1])
        if s[i+1] in h:
            h.remove(s[i+1])
        s[i]=h[0]
        i+=1
        x+=1
    i+=1
if n>1 and s[-1]==s[-2]:
    h=f[:]
    h.remove(s[-1])
    s[i]=h[0]
    x+=1
print(x)
d=''
for i in s:
    d+=i
print(d)


n=int(input())
s=list(input())+["*"]
a=['*']
l=list("GRB")
c=0
for i in range(n):
    if s[i]==a[-1]:
        for j in l:
            if j!=a[-1] and j!=s[i+1]:
                a.append(j)
                c+=1
                break
    else:
        a.append(s[i])
print(c)
print(''.join(a[1:]))

# url: https://codeforces.com/contest/1108/problem/D


def compatible(prev, *args):
    if not args:
        return next(iter(colour_set - {prev}))
    else:
        return next(iter(colour_set - {prev, args[0]}))


n_lamps = int(input())
garland = list(input())

colour_set = {'R', 'G', 'B'}
count = 0

for idx, lamp in enumerate(garland):

    if idx == 0:
        continue

    prev = garland[idx-1]
    if lamp == prev:
        if idx == len(garland)-1:
            garland[-1] = compatible(prev)
            count += 1
            continue

        nxt = garland[idx+1]
        garland[idx] = compatible(prev, nxt)
        count += 1

print(count)
print(''.join(garland))

h = 1
input()
p = 'x'
r = 1
t = []
for c in input().lower():
    if h != 1:
        p = next(iter(set('bgr') - {p, c}))
        t.append(p)
        h = 1
    if c != p:
        t.append(c)
    else:
        h = 2
        r += 1
    p = c
if h != 1:
    p = next(iter(set('bg') - {p}))
    t.append(p)
print(r - 1)
print(''.join(t).upper())


n = int(input())
s = input()
c = 'RGB'
ans = ''
ansk = 0
flag = True

for i in range(n-1):
    if flag:
        if s[i] == s[i+1]:
            if i == n-2:
                ans += s[i] + c[c.find(s[i])-1]
                ansk += 1
                print(ansk)
                print(ans)
                return
            else:
                for j in c:
                    if j != s[i] and j != s[i+2]:
                        break
                flag = False
                ansk += 1
                ans += s[i] + j
        else:
            ans += s[i] 
    else:
        flag = True

print(ansk)
print(ans+s[-1])