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-10-10 06:35:37 Alex Anderson
This problem seems similar to http://www.spoj.com/problems/PAAAARTY/

(Kata) : No. They 're completely different.

Last edit: 2015-10-11 14:21:05
2015-08-24 12:23:20 Anakar Parida
difficult

Last edit: 2015-08-24 12:26:19
2015-07-22 16:04:53
Some more test cases? It would really be helpful. I am getting wrong answer. Is the output just a single line or we have to format it in some special way?

(Kata) : I think those samples are clear enough. You only need to print a single line, no more requirement. Moreover, your algo (after fixed) still can't pass the time limit.

Last edit: 2015-07-22 22:34:52
2015-07-21 19:17:17
I'm getting a "runtime error (SIGSEGV)" error. Using C++, any idea what could be causing it?

Edit: nvm

Last edit: 2015-07-21 19:26:24
2015-07-21 10:42:07
i will give me a try, expect me ^^
2015-07-20 20:04:25
@min_25 .. can u give some hint
2015-07-19 03:00:16 Kata
Congratulation, min_25 ! You always write unimaginable codes !

(Reply from min_25) Thanks !

Last edit: 2015-07-19 08:33:09
2015-07-18 15:34:34 Kata
This is a hard problem, and you can't get accepted with a simple algorithm. But if you have an efficient algo, the time limit is relax. I think you should try the easier version (see "Resource")
2015-07-18 15:15:53
I see that everybody's getting a time Limit Exceeded Error.. Is the time limit reachable, because my code is very simple and I really don't see how to improve it...
2015-07-18 14:13:23 Kata
@evil99man :
They changed immediately when two cats talk. But you only need to find the final state.

Last edit: 2015-07-21 16:07:51
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.