시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)94625871.605%

문제

이환이는 4차 산업혁명 시대에 살고 있는 천재 5살 아기이다. 가위바위보를 즐기는 이환이는 집에서도 혼자 가위바위보를 하고 싶어서 창의력을 발휘해 카드를 이용한 게임을 만들었다. 게임을 하려면 먼저 '가위', '바위' 또는 '보'가 그려진 카드 $N$장을 일렬로 나열해 놓아야 한다. 그러고 나서, 가장 왼쪽에 있는 카드부터 차례대로 보면서 만약 그 카드가 바로 오른쪽에 있는 카드를 이긴다면 두 카드의 위치를 바꾸고, 그렇지 않다면 그대로 두는 것을 반복한다. 이렇게 마지막에서 두 번째 카드까지 한 번씩 훑어보면 놀이 한 번이 끝난다.

이환이는 이 놀이의 과정이 버블 정렬과 비슷하기 때문에 '가위바위보 버블 정렬'이라고 부르기로 했다. 카드의 승패 관계는 다음과 같다.

  • '가위'가 그려진 카드는 '보'가 그려진 카드를 이긴다.
  • '바위'가 그려진 카드는 '가위'가 그려진 카드를 이긴다.
  • '보'가 그려진 카드는 '바위'가 그려진 카드를 이긴다.

계산이 아주 빠른 이환이는 이 놀이를 무려 $T$번이나 했다! 피곤해진 이환이는 내일 이 놀이를 계속하기로 하고 잠을 자러 가려고 했으나, 카드 위를 지나가다 그만 카드들이 뒤섞여 버렸다. 이환이는 뛰어난 기억력을 가진 천재이기 때문에 맨 처음 카드들의 배열을 기억해 냈지만, 마지막 카드 배열은 기억하지 못했다. 놀이를 $T$번 한 후의 배열을 복원해서 이환이를 도와 주자.

입력

첫 번째 줄에는 카드의 개수 $N$($ 2 \leq N \leq 500\ 000 $)과 놀이를 한 횟수 $T$($1 \leq T \leq 1\ 000\ 000\ 000$)가 주어진다.

두 번째 줄에는 맨 처음 카드들의 배열을 나타내는 길이 $N$의 문자열이 주어진다. $i$번째 문자는 $i$번째 위치에 놓인 카드의 종류를 나타낸다. '가위'가 그려진 카드는 S, '바위'가 그려진 카드는 R, '보'가 그려진 카드는 P이다.

출력

$T$번 놀이를 한 후 카드들의 배열을 길이 $N$의 문자열로 출력한다. 마찬가지로 '가위'는 S, '바위'는 R, '보'는 P이다.

예제 입력 1

5 1
RSPSP

예제 출력 1

SRPPS

예제 입력 2

10 3
RSRRRRRRSR

예제 출력 2

SRRRRSRRRR

노트

첫 번째 예제에서, 이환이는 한 번의 놀이를 한다.

  1. 첫 번째 카드 R(바위)은 두 번째 카드 S(가위)를 이기므로 두 카드를 서로 바꾼다. 이때 배열은 SRPSP가 된다.
  2. 두 번째 카드 R(바위)은 세 번째 카드 P(보)에게 지므로 위치를 바꾸지 않는다.
  3. 세 번째 카드 P(보)는 네 번째 카드 S(가위)에게 지므로 위치를 바꾸지 않는다.
  4. 네 번째 카드 S(가위)는 마지막 카드 P(보)를 이기므로 두 카드를 서로 바꾼다. 이때 배열은 SRPPS가 된다.

따라서 놀이가 끝난 후 카드들의 배열은 SRPPS이다.

두 번째 예제에서, 이환이는 세 번의 놀이를 한다. 각 놀이가 끝난 후 카드들의 배열은 다음과 같이 변한다.

RSRRRRRRSR $\rightarrow$ SRRRRRRSRR $\rightarrow$ SRRRRRSRRR $\rightarrow$ SRRRRSRRRR

따라서 놀이가 끝난 후 카드들의 배열은 SRRRRSRRRR이다.