There are $n$ chips arranged in a circle, numbered from $1$ to $n$. 

Initially each chip has black or white color. Then $k$ iterations occur. During each iteration the chips change their colors according to the following rules. For each chip $i$, three chips are considered: chip $i$ itself and two its neighbours. If the number of white chips among these three is greater than the number of black chips among these three chips, then the chip $i$ becomes white. Otherwise, the chip $i$ becomes black. 

Note that for each $i$ from $2$ to $(n - 1)$ two neighbouring chips have numbers $(i - 1)$ and $(i + 1)$. The neighbours for the chip $i = 1$ are $n$ and $2$. The neighbours of $i = n$ are $(n - 1)$ and $1$.

The following picture describes one iteration with $n = 6$. The chips $1$, $3$ and $4$ are initially black, and the chips $2$, $5$ and $6$ are white. After the iteration $2$, $3$ and $4$ become black, and $1$, $5$ and $6$ become white.

 [Image] 

Your task is to determine the color of each chip after $k$ iterations.


-----Input-----

The first line contains two integers $n$ and $k$ $(3 \le n \le 200\,000, 1 \le k \le 10^{9})$ — the number of chips and the number of iterations, respectively.

The second line contains a string consisting of $n$ characters "W" and "B". If the $i$-th character is "W", then the $i$-th chip is white initially. If the $i$-th character is "B", then the $i$-th chip is black initially.


-----Output-----

Print a string consisting of $n$ characters "W" and "B". If after $k$ iterations the $i$-th chip is white, then the $i$-th character should be "W". Otherwise the $i$-th character should be "B".


-----Examples-----
Input
6 1
BWBBWW

Output
WBBBWW

Input
7 3
WBWBWBW

Output
WWWWWWW

Input
6 4
BWBWBW

Output
BWBWBW



-----Note-----

The first example is described in the statement.

The second example: "WBWBWBW" $\rightarrow$ "WWBWBWW" $\rightarrow$ "WWWBWWW" $\rightarrow$ "WWWWWWW". So all chips become white.

The third example: "BWBWBW" $\rightarrow$ "WBWBWB" $\rightarrow$ "BWBWBW" $\rightarrow$ "WBWBWB" $\rightarrow$ "BWBWBW".

Difficulty: interview

Starter code:

Solutions:
n, k = map(int, input().split())
a = list(input()) * 2

iter1 = [0] * (2 * n)
iter2 = [0] * (2 * n)
changes = 0
for i in range(1, 2 * n):
    if a[i] != a[i - 1]:
        changes += 1
    else:
        changes = 0
    iter1[i] = changes
changes = 0
for i in range(2 * n - 2, -1, -1):
    if a[i] != a[i + 1]:
        changes += 1
    else:
        changes = 0
    iter2[i] = changes

iters = [min(iter1[n + i], iter2[i]) for i in range(n)]
for i in range(n):
    if iters[i] > n // 2:
        iters[i] = 10 ** 9 + 1
    it = min(iters[i], k)
    if it % 2 != 0:
        if a[i] == "B":
            a[i] = "W"
        else:
            a[i] = "B"
print("".join(a[:n]))

import sys
input = sys.stdin.readline

n,k=list(map(int,input().split()))
S=input().strip()

ANS=["?"]*n

for i in range(n-1):
    if S[i]=="B":
        if S[i-1]=="B" or S[i+1]=="B":
            ANS[i]="B"

    else:
        if S[i-1]=="W" or S[i+1]=="W":
            ANS[i]="W"

if S[n-1]=="B":
    if S[n-2]=="B" or S[0]=="B":
        ANS[n-1]="B"

else:
    if S[n-2]=="W" or S[0]=="W":
        ANS[n-1]="W"


COMP=[]

count=1
now=ANS[0]

for i in range(1,n):
    if ANS[i]==ANS[i-1]:
        count+=1
    else:
        COMP.append([now,count])
        count=1
        now=ANS[i]

COMP.append([now,count])
hosei=0

if len(COMP)==1:
    if COMP[0][0]!="?":
        print(S)
    else:
        if k%2==0:
            print(S)
        else:
            ANS=[]
            for s in S:
                if s=="B":
                    ANS.append("W")
                else:
                    ANS.append("B")
            print("".join(ANS))
    return

if COMP[0][0]=="?" and COMP[-1][0]=="?":
    hosei=COMP[-1][1]
    COMP.pop()
    COMP[0][1]+=hosei

ANS2=[]

LEN=len(COMP)
if COMP[0][0]!="?":
    COMP.append(COMP[0])

for i in range(LEN):
    if COMP[i][0]!="?":
        ANS2.append(COMP[i])
    else:
        x=COMP[i][1]

        if x<=k*2:
            if COMP[i-1][0]==COMP[i+1][0]:
                ANS2.append([COMP[i-1][0],x])

            else:
                ANS2.append([COMP[i-1][0],x//2])
                ANS2.append([COMP[i+1][0],x//2])

        else:
            ANS2.append([COMP[i-1][0],k])
            ANS2.append(["?",x-2*k])
            ANS2.append([COMP[i+1][0],k])

#print(ANS2)
            
GOAL=[]
for x,y in ANS2:
    if x!="?":
        GOAL+=[x]*y
    else:
        if GOAL!=[]:
            if GOAL[-1]=="B":
                t=0
            else:
                t=1
        else:
            if ANS2[-1][0]=="B":
                t=0
            else:
                t=1

        for j in range(y):
            if j%2==0:
                if t==0:
                    GOAL.append("W")
                else:
                    GOAL.append("B")
            else:
                if t==0:
                    GOAL.append("B")
                else:
                    GOAL.append("W")

GOAL=GOAL[hosei:]+GOAL[:hosei]

print("".join(GOAL))

                    
                
            
            
            
                


n, m = [int(x) for x in input().split()]
s = input()

def lefti(i):
    return (n+i-1)%n
def left(i):
    return s[lefti(i)]
def righti(i):
    return (i+1)%n
def right(i):
    return s[righti(i)]
def inverse(c):
    return 'B' if c == 'W' else 'W'

res = [' ' for i in range(n)]
for i in range(n):
    cr = s[i]
    pr = left(i)
    nx = right(i)
    if cr == pr or cr == nx:
        res[i] = cr

all_empty = False
i = 0
while res[i] == ' ':
    i += 1
    if i >= n:
        all_empty = True
        break

if all_empty:
    for k in range(n):
        res[k] = s[k] if m % 2 == 0 else inverse(s[k])
else:
    krug = i
    i = righti(i)
    while i != krug:
        while res[i] != ' ' and i != krug:
            i = righti(i)
        if i == krug:
            break
        l = lefti(i)
        
        while res[i] == ' ':
            i = righti(i)
        r = i

        real_l = l
##        print(res)
        for j in range(m):
            res[righti(l)] = res[l]
            res[lefti(r)] = res[r]
##            print(res, l, r, i, m)
            
            l = righti(l)
            r = lefti(r)
            if righti(l) == r or l == r:
                break
        
    for k in range(n):
        if res[k] == ' ':
            res[k] = s[k] if m % 2 == 0 else inverse(s[k])

print("".join(res))

    

        


rev = {'B': 'W', 'W': 'B'}

n, k = list(map(int, input().split()))
a = list(input())

if all([a[0] == x for x in a]):
	print(''.join(a))
	return

f = [i for i in range(n)]
c = [1 for i in range(n)]

def getF(u):
	if f[u] == u:
		return u
	if f[f[u]] == f[u]:
		return f[u]
	f[u] = getF(f[u])
	return f[u]

def uniF(u, v):
	u, v = list(map(getF, (u, v)))
	if u == v:
		return
	f[u] = v
	c[v] += c[u]

for i in range(n):
	if a[i] == a[(i - 1) % n]:
		uniF(i, (i - 1) % n)
	if a[i] == a[(i + 1) % n]:
		uniF(i, (i + 1) % n)

p = []

for i in range(n):
	if getF(i) == i and c[i] > 1:
		p.append(i)

if len(p) == 0:
	if k % 2:
		a = list(map(rev.__getitem__, a))
	print(''.join(a))
	return

for i in range(len(p)):
	u = p[i]
	while a[(u + 1) % n] == a[p[i]]:
		u = (u + 1) % n
	v = p[(i + 1) % len(p)]
	while a[(v - 1) % n] == a[p[(i + 1) % len(p)]]:
		v = (v - 1) % n
	if v < u:
		v += n
	l = v - u - 1
	if 2 * k >= l:
		for i in range(u, u + l // 2 + 1):
			a[i % n] = a[u]
		for i in range(u + l // 2 + 1, v):
			a[i % n] = a[v % n]
	else:
		for i in range(u + 1, u + k + 1):
			a[i % n] = a[u]
		for i in range(v - k, v):
			a[i % n] = a[v % n]
		for i in range(u + k + 1, v - k):
			a[i % n] = rev[a[(i - 1) % n]]

print(''.join(a))


# 
# from __future__ import division

# input = raw_input
import math



## Make simpler structure:
class Same:
    def __init__(self,col, size, fro, to):
        self.size = size
        self.col = col
        self.fro = fro
        self.to = to

    def __repr__(self):
        return "Same({},{}, [{},{}))".format(self.col, self.size, self.fro, self.to)

class Alter:
    def __init__(self, size, fro, to):
        self.size = size
        self.fro = fro
        self.to = to
    def __repr__(self):
        return "Alter({}, [{},{}))".format(self.size, self.fro, self.to)

def simpl(lst):
    lst = lst[0] + lst + lst[-1]
    res = []
    prv = None
    streak_same = 0
    same_starts = 0
    for pos, curr in enumerate(lst):
        #print(pos, curr, prv, streak_same, same_starts)
        if curr == prv:
            if streak_same == 0:
                same_starts = pos-1
                streak_same = 2
            else: streak_same += 1
        else:
            if streak_same > 0:
                res.append(Same(prv, streak_same, same_starts, pos))
                assert streak_same == pos - same_starts
                same_starts = None
                streak_same = 0
        prv = curr
    if streak_same > 0:
        res.append(Same(prv, streak_same, same_starts, len(lst)))
        assert streak_same == len(lst) - same_starts

    # Insert alternating and strip the ends. First strip the ends (and change the indices):
    res[0].size -= 1
    res[-1].size -=1
    res[0].to -= 1
    res[-1].to -= 1
    for x in res[1:]:
      x.fro -= 1
      x.to -= 1

    # Append alternating:
    #print(res)
    new_res = []
    # all pairs (A0, A1), (A1, A2), ... (An-2, An-1)
    for x, y in zip(res, res[1:]):
      new_res.append(x)
      if x.to != y.fro:
        new_res.append(Alter(y.fro-x.to, x.to, y.fro))
    new_res.append(res[-1])
    return new_res

def other_col(x):
  return 'B' if x == 'W' else 'W'

def alter_col(start, size):
  oth = other_col(start)
  res = []
  for i in range(size):
    if i % 2 == 0:
      res.append(start)
    else: res.append(oth)
  return ''.join(res)

def compute_alter(size, prv_col, nxt_col, k):
  # Every step, size decreases by 2:
  size_after_k = max(0, size - 2*k)
  assert size % 2 == (1 if prv_col == nxt_col else 0)
  if size_after_k == 0:
    if prv_col == nxt_col:
      return prv_col * size
    # Otherwise it's split evenly in the two colors of prv_col, nxt_col
    else:
      return prv_col * (size //2) + nxt_col * (size // 2)
  else:
    alter_middle = alter_col(other_col(prv_col), size_after_k)
    return prv_col * k + alter_middle + nxt_col * k


def simulate(splitted, k):
  res = [splitted[0].col*splitted[0].size]
  if len(splitted) == 1: return res
  for i in range(1, len(splitted)-1):
    prv, curr, nxt = splitted[i-1], splitted[i], splitted[i+1]
    if isinstance(curr, Alter):
      assert isinstance(prv, Same) and isinstance(nxt, Same)
      alter_after_change = compute_alter(curr.size, prv.col, nxt.col, k)
      assert len(alter_after_change) == curr.size
      res.append(alter_after_change)
    else:
      res.append(curr.col * curr.size)
  res.append(splitted[-1].col * splitted[-1].size)
  return res

def test(lst, k):
  n = len(lst)
  # look for 2 in a row (there are at least 3:)
  two_in_row = None
  for i, (cur, prv) in enumerate(zip(lst, lst[1:] + lst[0])):
      if cur == prv:
          two_in_row = i
          break
  #print(list(enumerate(zip(lst, lst[1:] + lst[0]))))
  #print(two_in_row)

  if two_in_row is None:
      if k%2 == 0:
          return lst
      else:
          # flip it:
          return ''.join('B' if x == 'W' else 'W' for x in lst)

  # re-cut it so that start and end never change:
  #   i=_
  # BWBWBBWW
  #   i-^
  # print(lst)
  flip = i
  lst = lst[flip+1:] + lst[:flip+1]
  #print("Flipped: ", lst)
  smpl = simpl(lst)
  #print("Parsed: ", smpl)
  before_flip_res = simulate(smpl, k)
  #print("Simulated: ", before_flip_res)
  before_flip_res = ''.join(before_flip_res)
  after_flip = n-(flip+1)
  #print("First part:", before_flip_res[after_flip:])
  #print("Second part: ", before_flip_res[:after_flip])

  # flip it back:
  return before_flip_res[after_flip:] + before_flip_res[:after_flip]

def sim_slow(lst, k):
  for _ in range(k):
    nxt_lst = [None for _ in range(len(lst))]
    for i, curr in enumerate(lst):
      prv, curr, nxt = lst[i-1], lst[i], lst[(i+1) % len(lst)]
      nW = [prv, curr, nxt].count('W')
      nB = [prv, curr, nxt].count('B')
      if nW >= 2:
        nxt_lst[i] = 'W'
      else: nxt_lst[i] = 'B'
    lst = nxt_lst
  return ''.join(lst)

if False:
  import itertools
  for x in itertools.product("BW", "BW", "BW", "BW", "BW", "BW", "BW", "BW", "BW", "BW", "BW", "BW"):
    x = ''.join(x)
    for k in range(10):
      if sim_slow(x, k) != test(x, k):
        print(x, k, sim_slow(x, k), test(x, k))
        assert False

#t = int(input())
for _ in range(1):
  _, k = [int(x) for x in input().split()]
  lst = input()
  res = test(lst, k)
  # print("result: ", res)
  # print("\n")
  print(res)

# print(simpl(lst))


n, k = map(int, input().split())
a = list(input()) * 2
     
iter1 = [0] * (2 * n)
iter2 = [0] * (2 * n)
changes = 0
for i in range(1, 2 * n):
    if a[i] != a[i - 1]:
        changes += 1
    else:
        changes = 0
    iter1[i] = changes
changes = 0
for i in range(2 * n - 2, -1, -1):
    if a[i] != a[i + 1]:
        changes += 1
    else:
        changes = 0
    iter2[i] = changes
     
iters = [min(iter1[n + i], iter2[i]) for i in range(n)]
for i in range(n):
    if iters[i] > n // 2:
        iters[i] = 10 ** 9 + 1
    it = min(iters[i], k)
    if it % 2 != 0:
        if a[i] == "B":
            a[i] = "W"
        else:
            a[i] = "B"
print("".join(a[:n]))

n, k = [int(i) for i in input().split()]
col = [0 if d == "W" else 1 for d in input()]


offs = 0
if col[0] != col[-1]:
    offs = -1
    for i in range(n-1):
        if col[i] == col[i+1]:
            offs = i+1
            break
    if offs == -1:
        if k % 2 == 0:
            print(''.join([["W", "B"][col[i]] for i in range(n)]))
        else:
            print(''.join([["B", "W"][col[i]] for i in range(n)]))
        return
    col = col[offs:] + col[:offs] 

# print(col)
isalt = [0]*n
for i in range(1, n-1):
    if col[i-1] != col[i] and col[i] != col[i+1]:
        isalt[i] = 1



sides = [[-1,-1] for i in range(n)]

ll = 0
for i in range(n):
    if isalt[i]:
        sides[i][0] = ll
    else:
        ll = i + 1
rr = 0
for i in range(n-1, -1, -1):
    if isalt[i]:
        sides[i][1] = rr
    else:
        rr = i - 1


even = k%2 == 0
ans = [0] * n
for i in range(n):
    if isalt[i] == 0:
        ans[i] = col[i]
    else:
        bb = sides[i]
        if i - bb[0] < bb[1] - i:
            dist = i - bb[0]
            nei = col[bb[0] - 1]
        else:
            dist = bb[1] - i
            nei = col[bb[1]+1]
        if dist + 1 <= k:
            ans[i] = nei
        else:
            if even:
                ans[i] = col[i]
            else:
                ans[i] = 1 - col[i]



# print(ans)
if offs != 0:
    offs = n - offs
    ans = ans[offs:] + ans[:offs]

# print(offs, ans)

print(''.join([["W", "B"][ans[i]] for i in range(n)]))


n, k = map(int, input().split())
a = list(input()) * 2
 
iter1 = [0] * (2 * n)
iter2 = [0] * (2 * n)
changes = 0
for i in range(1, 2 * n):
    if a[i] != a[i - 1]:
        changes += 1
    else:
        changes = 0
    iter1[i] = changes
changes = 0
for i in range(2 * n - 2, -1, -1):
    if a[i] != a[i + 1]:
        changes += 1
    else:
        changes = 0
    iter2[i] = changes
 
iters = [min(iter1[n + i], iter2[i]) for i in range(n)]
for i in range(n):
    if iters[i] > n // 2:
        iters[i] = 10 ** 9 + 1
    it = min(iters[i], k)
    if it % 2 != 0:
        if a[i] == "B":
            a[i] = "W"
        else:
            a[i] = "B"
print("".join(a[:n]))

"""
def get(ch):
    if(ch=='W'):
        return 'B'
    return 'W'

n,k=map(int,input().split())
s=input()

pos=[0]*(n)

for i in range(0,len(s)):

    if(s[i]==s[(i+1)%n]):
        if(s[i]=='W'):
            pos[i]=1
            pos[(i+1)%n]=1
        else:
            pos[i]=2
            pos[(i+1)%n]=2


temp=0
str1=0
itr=[]

for i in range(0,len(pos)):
    if(pos[i]>0 and temp==0):
        temp=1
        str1=i
    itr.append([10**9+7,'W'])

  
if(temp==1):
    for i in range(str1,str1+n):
        if(pos[(i%n)]>0):
            curr=pos[(i%n)]
            ptr=i
        else:
            itr[(i%n)][0]=i-ptr
            if(curr==1):
                itr[(i%n)][1]='W'
            else:
                itr[(i%n)][1]='B'


    for i in range(str1,str1-n,-1):
        if(pos[(i%n)]>0):
            curr=pos[(i%n)]
            ptr=i
        else:
            if(ptr-i<itr[(i%n)][0]):
                itr[(i%n)][0]=ptr-i
                if(curr==1):
                    itr[(i%n)][1]='W'
                else:
                    itr[(i%n)][1]='B'


ans=''
for i in range(0,len(s)):
    if(itr[i][0]>=k):
        ans+=itr[i][1]
    else:
        if(k%2==0):
            ans+=s[i]
        else:
            ans+=get(s[i])

print(ans)


"""



def get(ch):
    if(ch=='W'):
        return 'B'
    return 'W'

n,k=list(map(int,input().split()))
s=input()

pos=[0]*(n)

for i in range(0,len(s)):

    if(s[i]==s[(i+1)%n]):
        if(s[i]=='W'):
            pos[i]=1
            pos[(i+1)%n]=1
        else:
            pos[i]=2
            pos[(i+1)%n]=2


#print('pos',pos)

temp=0
str1=0
itr=[]

for i in range(0,len(pos)):
    if(pos[i]>0 and temp==0):
        temp=1
        str1=i
    itr.append([10**9+7,'W'])

#print('itr',itr)
if(temp==1):
    for i in range(str1,str1+n):
        if(pos[(i%n)]>0):
            curr=pos[(i%n)]
            ptr=i
        else:
            itr[(i%n)][0]=i-ptr
            if(curr==1):
                itr[(i%n)][1]='W'
            else:
                itr[(i%n)][1]='B'

    #print('inside itr',itr)


    for i in range(str1,str1-n,-1):
        if(pos[(i%n)]>0):
            curr=pos[(i%n)]
            ptr=i
        else:
            if(ptr-i<itr[(i%n)][0]):
                itr[(i%n)][0]=ptr-i
                if(curr==1):
                    itr[(i%n)][1]='W'
                else:
                    itr[(i%n)][1]='B'

    #print('inside itr',itr)


ans=''
for i in range(0,len(s)):
    if(pos[i]>0):
        ans+=s[i]
    else:
        if(itr[i][0]<=k):
            ans+=itr[i][1]
        else:
            if(k%2==0):
                ans+=s[i]
            else:
                ans+=get(s[i])

print(ans)


    


























            
    



























            
    


def get(ch):
    if(ch=='W'):
        return 'B'
    return 'W'

n,k=list(map(int,input().split()))
s=input()

pos=[0]*(n)

for i in range(0,len(s)):

    if(s[i]==s[(i+1)%n]):
        if(s[i]=='W'):
            pos[i]=1
            pos[(i+1)%n]=1
        else:
            pos[i]=2
            pos[(i+1)%n]=2


temp=0
str1=0
itr=[]

for i in range(0,len(pos)):
    if(pos[i]>0 and temp==0):
        temp=1
        str1=i
    itr.append([10**9+7,'W'])

if(temp==1):
    for i in range(str1,str1+n):
        if(pos[(i%n)]>0):
            curr=pos[(i%n)]
            ptr=i
        else:
            itr[(i%n)][0]=i-ptr
            if(curr==1):
                itr[(i%n)][1]='W'
            else:
                itr[(i%n)][1]='B'

    for i in range(str1,str1-n,-1):
        if(pos[(i%n)]>0):
            curr=pos[(i%n)]
            ptr=i
        else:
            if(ptr-i<itr[(i%n)][0]):
                itr[(i%n)][0]=ptr-i
                if(curr==1):
                    itr[(i%n)][1]='W'
                else:
                    itr[(i%n)][1]='B'

ans=''
for i in range(0,len(s)):
    if(pos[i]>0):
        ans+=s[i]
    else:
        if(itr[i][0]<=k):
            ans+=itr[i][1]
        else:
            if(k%2==0):
                ans+=s[i]
            else:
                ans+=get(s[i])

print(ans)