문제
J, O, I로 이루어진 길이 \(N\)인 문자열 \(S\)가 있다. JOI 군은 문자열 \(S\)에 대해, 더 이상 아래 연산을 할 수 없을 때까지 다음 연산을 반복한다.
연산 반복은 반드시 종료하며, 연산 순서와 관계없이 최종 문자열 상태가 유일하게 정해짐을 증명할 수 있다. 처음 문자열 \(S\)의 정보가 주어졌을 때, 최종 문자열 \(S\)를 구하는 프로그램을 작성하라. |
입력
입력은 다음 형식으로 주어진다.
\(N\)
\(S\)
제약 조건
- \(3 \le N \le 500{,}000\)
- \(S\)는 J, O, I로 이루어진 길이 \(N\)인 문자열이다.
- \(N\)은 정수이다.
부분문제
- (14점) \(N \le 100\)
- (27점) \(N\)은 3의 배수이며, \(S\)는 JOI를 \(N/3\)번 반복한 문자열이다.
- (29점) \(2 \le k \le N\)을 만족하는 정수 \(k\)가 존재하여, \(S\)의 1번째부터 \(k\)번째 문자까지는 모두 J이고, \(k+1\)번째 이후에는 J가 없다.
- (30점) 추가 제약 조건 없음.
출력
다음 형식으로 출력한다.
최종 문자열 \(S\)를 1줄에 출력한다.
예시 1
입력
6
JOIJOI
출력
OIOIJJ
설명
예를 들어, JOI 군이 다음과 같이 연산할 수 있다.
처음에 \(S =\) JOIJOI이다.
- 1번째부터 3번째 문자에 연산을 수행한다. \(S =\) OIJJOI가 된다.
- 4번째부터 6번째 문자에 연산을 수행한다. \(S =\) OIJOIJ가 된다.
- 3번째부터 5번째 문자에 연산을 수행한다. \(S =\) OIOIJJ가 된다.
더 이상 연산할 수 없으므로 OIOIJJ를 출력한다.
예시 2
입력
8
JJJOIOIO
출력
OIOIJJJO
예시 3
입력
20
JJOIJOIJOOIJOIIJJOIO
출력
OIOIJJJJOOIOIJIOIJJO