Dvergurinn Franek hefur alltaf elskað alls kyns leiki. Dag einn var hann aðgrams í dóti pabba síns uppi á háalofti og fann gamla leikjatölvu með því sem virtist vera Tetris-leikur. Þótt hann líktist hinum kunnuglega leik voru nokkrar reglur hans öðruvísi.

Leikurinn er spilaður á upphaflega tómu borði af breidd $10$ og ótakmarkaðri hæð. Kubbar falla ofan frá, einn af öðrum, í nákvæmlega þeirri röð sem gefin er í inntakinu.

Það eru aðeins tvær gerðir af kubbum:

• I-kubburinn, lagaður eins og lóðrétt stöng af hæð $4$ og breidd $1$.
• O-kubburinn, lagaður eins og heill ferningur af hæð $2$ og breidd $2$.

Þegar kubbur birtist verður Franek að velja hvar á að láta hann falla:

• Hægt er að láta I-kubb falla í hvaða dálk sem er af dálkunum $10$.
• Hægt er að láta O-kubb falla þannig að báðir dálkar hans rúmist مکملlega innan borðsins (það er að segja, þannig að hann byrji í hvaða dálki sem er frá $1$ til $9$).

Um leið og kubbur byrjar að falla sígur hann lóðrétt niður þar til hann lendir ofan á kubbum sem fyrir eru eða á botni borðsins. Ekki er hægt að snúa kubbum, færa þá til hliðar í loftinu eða skipta þeim í hluta. Eftir að kubburinn lendir fyllast allir reitir sem hann hylur.

Í hvert sinn sem lárétt röð á borðinu fyllist alveg af kubbum (sem þýðir að allir $10$ dálkarnir hafa kubb í þeirri hæð), hverfur sú röð. Allir kubbar fyrir ofan hana færast niður um eina einingu. Ef nokkrar raðir fyllast á sama tíma hverfa þær allar saman.

Þú skorar eitt tetris í hvert sinn sem nákvæmlega fjórar raðir hverfa samtímis. Markmið leiksins er að skora eins mörg tetris og mögulegt er.

Fyrsta borðið sýnir dæmi um uppsetningu kubba. Eftir að I-kubbi er sleppt í $8$. dálkinn byrjar hann að falla eins og sýnt er á öðru og þriðja borðinu. Eftir það hverfa neðstu fjórar raðirnar, sem gefur eitt tetris og leiðir til fjórða borðsins.

Þar sem Franek er keppnisglaður lítill dvergur vill hann ná hámarksstigum! Hann er hins vegar ekki nógu góður í leiknum, svo þú verður að hjálpa honum. Með því að vita röð kubbanna fyrirfram skaltu hjálpa Franek að ákvarða hámarksfjölda tetrisa sem hann getur náð ef hann spilar á besta mögulega hátt. Að auki skaltu gefa upp runu af leikjum sem nær þessum stigafjölda.

Inntak

Fyrsta línan inniheldur eina heiltölu $N$, fjölda kubba. Önnur línan inniheldur streng af lengd $N$, sem samanstendur eingöngu af stöfunum I og O, og lýsir röð kubbanna frá þeim fyrsta til þess síðasta.

Úttak

Í fyrstu línunni skaltu prenta eina heiltölu sem er hámarksfjöldi tetrisa sem Franek getur náð. Í annarri línunni skaltu prenta runu af $N$ heiltölum $c_1, c_2, \dots, c_N$, þar sem $c_i$ er dálkurinn sem láta á $i$-ta kubbinn falla í ($1$-vísað). Fyrir I-kubb verður $c_i$ að uppfylla $1 \le c_i \le 10$. Fyrir O-kubb vísar $c_i$ til vinstri dálks hans og verður að uppfylla $1 \le c_i \le 9$.

Ef fleiri en ein besta runa er til máttu prenta hverja sem er af þeim.

Takmarkanir

$1 \le N \le 200\,000$.

Dæmi

Inntak 1

10
IIOIOIOOII

Úttak 1

1
1 2 3 5 3 6 7 7 9 10

Athugasemd

Úttakið sem sýnt er er aðeins ein gild runa af leikjum; aðrar runur geta einnig náð sama hámarksfjölda tetrisa.