BLCATS - Magical colorful cats (hard)

There is a circle of n cats, includes white cats, red cats and green cats. When two cats of different colors talk with each other, they both change to third color. If they have same color, nothing will happen.

At each step, the 1st cat talks with 2nd cat, the 2nd cat talks with the 3rd cat,… and the nth cat talks with 1st cat.

Given the original color of n cats, your task is find the color of n cats after k steps.

Input

  • First line : n and k (1 ≤ n ≤ 50000, 1 ≤ k ≤ 109)
  • Second line : n characters, the i-th charater denotes color of the i-th cat at first state

Output

  • n charaters denotes the color of n cats after k steps.

Example

Input:
3 1
GRR

Output:
RGR
Input:
5 4
WRWRW

Output:
GGGWG

Note: Before solving this problem, you may want to try COLORCAT


Added by:Kata
Date:2015-07-17
Time limit:5s-10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:COLORCAT

hide comments
2015-07-18 14:07:47 Pranjal Shankhdhar
all colors are changed after the whole step or just after a cat talks?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.