Lýsing á verkefni

Gefinn er strengur $S$ af lengd $N$ sem samanstendur af J, O og I. JOI-kun endurtekur eftirfarandi aðgerð á strenginn $S$ þar til ekki er hægt að framkvæma fleiri aðgerðir:

• Veldu $1$ stað í $S$ þar sem J, O og I koma samfellt fyrir í þessari röð, og skiptu þeim hluta út fyrir O, I og J í þessari röð.

Sanna má að endurtekning aðgerðanna tekur alltaf enda og að lokastaða strengsins er ótvírætt ákvörðuð óháð því hvernig aðgerðirnar eru framkvæmdar.

Gefinn er upphaflegi strengurinn $S$. Skrifið forrit til að finna lokastrenginn $S$.

Takmarkanir

• $3 \le N \le 500000$.
• $S$ er strengur af lengd $N$ sem samanstendur af J, O og I.
• $N$ er heiltala.

Undirverkefni

1. ($14$ stig) $N \le 100$.
2. ($27$ stig) $N$ er margfeldi af $3$, og $S$ er JOI endurtekið $N / 3$ sinnum.
3. ($29$ stig) Til er heiltala $k$ ($2 \le k \le N$) þannig að $1$. til $k$. stafur $S$ eru allir J, en $(k + 1)$. stafur og næstu stafir á eftir eru ekki J.
4. ($30$ stig) Engar viðbótartakmarkanir.

Inntak

Inntakið er gefið úr staðalinntaki á eftirfarandi sniði:

N
S

Úttak

Prentið lokastrenginn $S$ í $1$ línu á staðalúttak.

Dæmi

Dæmi um inntak 1

6
JOIJOI

Dæmi um úttak 1

OIOIJJ

Til dæmis getur JOI-kun framkvæmt aðgerðirnar á eftirfarandi hátt.

Í upphafi er $S =$ JOIJOI.

1. Framkvæmir aðgerðina á $1$. til $3$. staf. Þá verður $S =$ OIJJOI.
2. Framkvæmir aðgerðina á $4$. til $6$. staf. Þá verður $S =$ OIJOIJ.
3. Framkvæmir aðgerðina á $3$. til $5$. staf. Þá verður $S =$ OIOIJJ.

Þar sem ekki er hægt að framkvæma fleiri aðgerðir skal prenta OIOIJJ.

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefna $1, 2, 4$.

Dæmi um inntak 2

8
JJJOIOIO

Dæmi um úttak 2

OIOIJJJO

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefna $1, 3, 4$.

Dæmi um inntak 3

20
JJOIJOIJOOIJOIIJJOIO

Dæmi um úttak 3

OIOIJJJJOOIOIJIOIJJO

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefna $1, 4$.