Problembeskrivelse

Det finnes en streng $S$ med lengde $N$ som består av J, O og I. JOI-kun gjentar følgende operasjon på strengen $S$ helt til det ikke lenger er mulig å utføre flere operasjoner:

• Velg $1$ sted i $S$ der J, O og I står sammenhengende i denne rekkefølgen, og erstatt denne delen med O, I og J i denne rekkefølgen.

Det kan bevises at gjentakelsen av operasjoner alltid avsluttes, og at den endelige tilstanden til strengen er entydig bestemt uavhengig av hvordan operasjonene utføres.

Gitt informasjonen om den opprinnelige strengen $S$, skriv et program for å finne den endelige strengen $S$.

Begrensninger

• $3 \le N \le 500000$.
• $S$ er en streng med lengde $N$ som består av J, O og I.
• $N$ er et heltall.

Deloppgaver

1. ($14$ poeng) $N \le 100$.
2. ($27$ poeng) $N$ er et multiplum av $3$, og $S$ er JOI gjentatt $N / 3$ ganger.
3. ($29$ poeng) Det finnes et heltall $k$ ($2 \le k \le N$) slik at det $1$. til det $k$. tegnet i $S$ alle er J, mens det $(k + 1)$. og påfølgende tegn ikke er J.
4. ($30$ poeng) Ingen ytterligere begrensninger.

Inndata

Inndataene gis fra standard inndata i følgende format:

N
S

Utdata

Skriv ut den endelige strengen $S$ på $1$ linje til standard utdata.

Eksempel

Eksempelinndata 1

6
JOIJOI

Eksempelutdata 1

OIOIJJ

For eksempel kan JOI-kun utføre operasjonene som følger.

Til å begynne med er $S =$ JOIJOI.

1. Utfør operasjonen på det $1$. til $3$. tegnet. Da blir $S =$ OIJJOI.
2. Utfør operasjonen på det $4$. til $6$. tegnet. Da blir $S =$ OIJOIJ.
3. Utfør operasjonen på det $3$. til $5$. tegnet. Da blir $S =$ OIOIJJ.

Siden det ikke er mulig å utføre flere operasjoner, skriv ut OIOIJJ.

Disse eksempelinndataene tilfredsstiller begrensningene i deloppgave $1, 2, 4$.

Eksempelinndata 2

8
JJJOIOIO

Eksempelutdata 2

OIOIJJJO

Disse eksempelinndataene tilfredsstiller begrensningene i deloppgave $1, 3, 4$.

Eksempelinndata 3

20
JJOIJOIJOOIJOIIJJOIO

Eksempelutdata 3

OIOIJJJJOOIOIJIOIJJO

Disse eksempelinndataene tilfredsstiller begrensningene i deloppgave $1, 4$.