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: HARD
Tags: Implementation

Constructive algorithms

Starter code:

Solutions:
(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
		for j in range(m):
			res[righti(l)] = res[l]
			res[lefti(r)] = res[r]
			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))


(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)]))
		exit()
	col = col[offs:] + col[:offs]
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
		elif even:
			ans[i] = col[i]
		else:
			ans[i] = 1 - col[i]
if offs != 0:
	offs = n - offs
	ans = ans[offs:] + ans[:offs]
print(''.join([['W', 'B'][ans[i]] for i in range(n)]))


rev = {'B': 'W', 'W': 'B'}
(n, k) = map(int, input().split())
a = list(input())
if all(map(lambda x: a[0] == x, a)):
	print(''.join(a))
	exit()
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) = 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 = map(rev.__getitem__, a)
	print(''.join(a))
	exit()
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))


import math

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):
		if curr == prv:
			if streak_same == 0:
				same_starts = pos - 1
				streak_same = 2
			else:
				streak_same += 1
		elif 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
	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
	new_res = []
	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):
	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
		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)
	two_in_row = None
	for (i, (cur, prv)) in enumerate(zip(lst, lst[1:] + lst[0])):
		if cur == prv:
			two_in_row = i
			break
	if two_in_row is None:
		if k % 2 == 0:
			return lst
		else:
			return ''.join(('B' if x == 'W' else 'W' for x in lst))
	flip = i
	lst = lst[flip + 1:] + lst[:flip + 1]
	smpl = simpl(lst)
	before_flip_res = simulate(smpl, k)
	before_flip_res = ''.join(before_flip_res)
	after_flip = n - (flip + 1)
	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
for _ in range(1):
	(_, k) = [int(x) for x in input().split()]
	lst = input()
	res = test(lst, k)
	print(res)


(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) = 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
		elif 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]
	elif itr[i][0] <= k:
		ans += itr[i][1]
	elif k % 2 == 0:
		ans += s[i]
	else:
		ans += get(s[i])
print(ans)


import sys
input = sys.stdin.readline
(n, k) = 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'
	elif 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'
elif 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)
	elif k % 2 == 0:
		print(S)
	else:
		ANS = []
		for s in S:
			if s == 'B':
				ANS.append('W')
			else:
				ANS.append('B')
		print(''.join(ANS))
	sys.exit()
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])
GOAL = []
for (x, y) in ANS2:
	if x != '?':
		GOAL += [x] * y
	else:
		if GOAL != []:
			if GOAL[-1] == 'B':
				t = 0
			else:
				t = 1
		elif 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')
			elif t == 0:
				GOAL.append('B')
			else:
				GOAL.append('W')
GOAL = GOAL[hosei:] + GOAL[:hosei]
print(''.join(GOAL))