JOI エリミネーター (JOI Eliminator)

J, O, I からなる長さ \(N\) の文字列 \(S\) がある． JOI 君は文字列 \(S\) に対して，以下の操作をそれ以上操作が行えなくなるまで繰り返す．

• \(S\) の中で J, O, I がこの順で連続して並んでいる箇所を \(1\) つ選び，その部分を O, I, J の並びに置き換える．

操作の繰り返しは必ず終了し，また操作の方法によらず最終的な文字列の状態が一意に定まることが証明できる．

はじめの文字列 \(S\) の情報が与えられたとき，最終的な文字列 \(S\) を求めるプログラムを作成せよ．

• \(3 \leqq N \leqq 500\,000\)．
• \(S\) は J, O, I からなる長さ \(N\) の文字列である．
• \(N\) は整数である．

1. (\(14\) 点) \(N \leqq 100\)．
2. (\(27\) 点) \(N\) は \(3\) の倍数で， \(S\) は JOI を \(N / 3\) 回繰り返したものである．
3. (\(29\) 点) ある整数 \(k\) \((2 \leqq k \leqq N\)) が存在して， \(S\) の \(1\) 文字目から \(k\) 文字目まではすべて J であり，一方 \(k + 1\) 文字目以降は J でない．
4. (\(30\) 点) 追加の制約はない．

入力は以下の形式で与えられる．

\(N\)
\(S\)

最終的な文字列 \(S\) を \(1\) 行で出力せよ．

JOI 2026 · JCIOI · CC BY-SA 4.0