| Codeforces Round 592 (Div. 2) |
|---|
| Закончено |
На круглом столе расположены $$$n$$$ фишек, которые лежат по кругу. Все фишки пронумерованы подряд целыми числами от $$$1$$$ до $$$n$$$.
Изначально каждая фишка имеет черный или белый цвет. После этого происходит $$$k$$$ итераций. На каждой итерации фишки становятся черными или белыми в соответствии со следующими правилами. Для каждой фишки $$$i$$$ подсчитывается количество белых и черных фишек на предыдущей итерации. В подсчете участвует фишка $$$i$$$, а также ее непосредственные соседи слева и справа. Если белых фишек было больше, то фишка $$$i$$$ должна стать белого цвета. В противном случае, фишка $$$i$$$ должна стать черного цвета.
Обратите внимание, что для всех $$$i$$$ от $$$2$$$ до $$$(n - 1)$$$ соседняя фишка слева имеет номер $$$(i - 1)$$$, а соседняя фишка справа имеет номер $$$(i + 1)$$$. Для $$$i = 1$$$ соседняя фишка слева имеет номер $$$n$$$, а соседняя фишка справа имеет номер $$$2$$$. Для $$$i = n$$$ соседняя фишка слева имеет номер $$$(n - 1)$$$, а соседняя фишка справа имеет номер $$$1$$$.
На рисунке представлено изменение цветов фишек после одной итерации для случая $$$n = 6$$$. Фишки $$$1$$$, $$$3$$$ и $$$4$$$ изначально черного цвета, а фишки $$$2$$$, $$$5$$$ и $$$6$$$ — белого. После одной итерации фишки $$$2$$$, $$$3$$$ и $$$4$$$ становятся черного цвета, а фишки $$$1$$$, $$$5$$$ и $$$6$$$ — белого.
Перед вами стоит задача определить какого цвета будут все фишки после $$$k$$$ итераций.
В первой строке следуют два целых числа $$$n$$$ и $$$k$$$ $$$(3 \le n \le 200\,000, 1 \le k \le 10^{9})$$$ — количество фишек и количество итераций.
Во второй строке следует строка, состоящая из $$$n$$$ букв «W» и «B». Если $$$i$$$-й символ строки равен «W», то изначально $$$i$$$-я фишка имеет белый цвет. Если $$$i$$$-й символ строки равен «B», то изначально $$$i$$$-я фишка имеет черный цвет.
Выведите строку, состоящую из $$$n$$$ букв «W» и «B». Если после $$$k$$$ итераций $$$i$$$-я фишка будет иметь белый цвет, то $$$i$$$-й символ выведенной строки должен быть равен «W». В противном случае, $$$i$$$-й символ выведенной строки должен быть равен «B».
6 1 BWBBWW
WBBBWW
7 3 WBWBWBW
WWWWWWW
6 4 BWBWBW
BWBWBW
Первый пример подробно разобран в условии.
Во втором примере цвета фишек будут изменяться следующим образом: «WBWBWBW» $$$\rightarrow$$$ «WWBWBWW» $$$\rightarrow$$$ «WWWBWWW» $$$\rightarrow$$$ «WWWWWWW». Таким образом, после трех итераций все фишки будут белого цвета.
В третьем примере цвета фишек будут изменяться следующим образом: «BWBWBW» $$$\rightarrow$$$ «WBWBWB» $$$\rightarrow$$$ «BWBWBW» $$$\rightarrow$$$ «WBWBWB» $$$\rightarrow$$$ «BWBWBW».
