Tehtävänanto

Annetaan pituutta $N$ oleva merkkijono $S$, joka koostuu merkeistä J, O ja I. JOI-kun toistaa seuraavaa operaatiota merkkijonolle $S$, kunnes operaatioita ei voida enää suorittaa:

• Valitse merkkijonosta $S$ $1$ kohta, jossa J, O ja I esiintyvät peräkkäin tässä järjestyksessä, ja korvaa kyseinen osa merkeillä O, I ja J tässä järjestyksessä.

Voidaan todistaa, että operaatioiden toistaminen päättyy aina ja että merkkijonon lopullinen tila määräytyy yksikäsitteisesti riippumatta siitä, miten operaatiot suoritetaan.

Kun alkuperäinen merkkijono $S$ annetaan, kirjoita ohjelma, joka selvittää lopullisen merkkijonon $S$.

Rajoitukset

• $3 \le N \le 500000$.
• $S$ on pituutta $N$ oleva merkkijono, joka koostuu merkeistä J, O ja I.
• $N$ on kokonaisluku.

Osatehtävät

1. ($14$ pistettä) $N \le 100$.
2. ($27$ pistettä) $N$ on luvun $3$ monikerta, ja $S$ on JOI toistettuna $N / 3$ kertaa.
3. ($29$ pistettä) On olemassa kokonaisluku $k$ ($2 \le k \le N$) siten, että merkkijonon $S$ merkit $1$. merkistä $k$. merkkiin ovat kaikki J, kun taas $(k + 1)$. merkki ja sitä seuraavat merkit eivät ole J.
4. ($30$ pistettä) Ei lisärajoituksia.

Syöte

Syöte annetaan vakiosyötteestä seuraavassa muodossa:

N
S

Tuloste

Tulosta lopullinen merkkijono $S$ vakiotulosteeseen $1$ riville.

Esimerkki

Esimerkkisyöte 1

6
JOIJOI

Esimerkkituloste 1

OIOIJJ

JOI-kun voi suorittaa operaatiot esimerkiksi seuraavasti.

Aluksi $S =$ JOIJOI.

1. Suoritetaan operaatio $1$.–$3$. merkille. Tällöin $S =$ OIJJOI.
2. Suoritetaan operaatio $4$.–$6$. merkille. Tällöin $S =$ OIJOIJ.
3. Suoritetaan operaatio $3$.–$5$. merkille. Tällöin $S =$ OIOIJJ.

Koska operaatioita ei voida enää suorittaa, tulostetaan OIOIJJ.

Tämä esimerkkisyöte täyttää osatehtävien $1, 2, 4$ rajoitukset.

Esimerkkisyöte 2

8
JJJOIOIO

Esimerkkituloste 2

OIOIJJJO

Tämä esimerkkisyöte täyttää osatehtävien $1, 3, 4$ rajoitukset.

Esimerkkisyöte 3

20
JJOIJOIJOOIJOIIJJOIO

Esimerkkituloste 3

OIOIJJJJOOIOIJIOIJJO

Tämä esimerkkisyöte täyttää osatehtävien $1, 4$ rajoitukset.