配点: 100 点
問題文
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 是一个整数。
小課題
- (14 点) N \leqq 100.
- (27 点) N 是 3 的倍数,
重复 S 是
JOI在 N / 3 次。 - (29 点)一些整数 k (2 \leqq k \leqq N)存在, S 的 1 从第一个字符开始 k 直到第一个字符的所有内容
J,同时 k + 1 字符之后 它不是J。 - (30 点)没有额外的限制。 选择
入力
输入格式如下。
N S
出力
最终字符串 S 在 1 行。 在
入力例 1
6 JOIJOI
出力例 1
OIOIJJ
例如,JOI 可以执行以下操作。
最初,S = JOIJOI 。
- 1 从第一个字符开始 3 对第一个字符执行操作。 S =
OIJJOI变为。 - 4 从第一个字符开始 6 对第一个字符执行操作。 S =
OIJOIJ变为。 - 3 从第一个字符开始 5 对第一个字符执行操作。 S =
OIOIJJ变为。
由于无法执行进一步的操作,OIOIJJ 。
此输入示例是一个小作业。 1,2,4 满足约束。
入力例 2
8 JJJOIOIO
出力例 2
OIOIJJJO
此输入示例是一个小作业。 1,3,4 满足约束。
入力例 3
20 JJOIJOIJOOIJOIIJJOIO
出力例 3
OIOIJJJJOOIOIJIOIJJO
此输入示例是一个小作业。 1,4 满足约束。