Kääpiö Franek on aina rakastanut kaikenlaisia pelejä. Eräänä päivänä hän kävi läpi isänsä tavaroita ullakolla ja löysi vanhan pelikonsolin, jossa oli Tetris-peliltä vaikuttava peli. Vaikka se muistutti tuttua peliä, osa sen säännöistä oli erilaisia.
Peliä pelataan aluksi tyhjällä pelilaudalla, jonka leveys on $10$ ja korkeus rajoittamaton. Palikat putoavat ylhäältä yksi kerrallaan täsmälleen syötteessä annetussa järjestyksessä.
Palikoita on vain kahta tyyppiä:
I-palikka, joka on muodoltaan pystysuora palkki, jonka korkeus on $4$ ja leveys $1$.O-palikka, joka on muodoltaan umpinainen neliö, jonka korkeus on $2$ ja leveys $2$.
Kun palikka ilmestyy, Franekin on valittava, mihin hän pudottaa sen:
I-palikan voi pudottaa mihin tahansa $10$ sarakkeesta.O-palikan voi pudottaa siten, että sen kaksi saraketta mahtuvat kokonaan laudan sisälle (eli alkaen mistä tahansa sarakkeesta välillä $1$–$9$).
Kun palikka alkaa pudota, se laskeutuu pystysuoraan, kunnes se laskeutuu olemassa olevien lohkojen päälle tai laudan pohjalle. Palikoita ei voi kääntää, liikuttaa sivuttain ilmassa eikä jakaa osiin. Kun palikka on laskeutunut, kaikki sen peittämät ruudut täyttyvät.
Aina kun laudan vaakasuora rivi täyttyy kokonaan lohkoista (mikä tarkoittaa, että kaikissa $10$ sarakkeessa on lohko kyseisellä korkeudella), tämä rivi katoaa. Kaikki sen yläpuolella olevat lohkot siirtyvät yhden yksikön alaspäin. Jos useita rivejä täyttyy samanaikaisesti, ne kaikki katoavat yhdessä.
Saat yhden tetriksen (tetris) aina, kun täsmälleen neljä riviä katoaa samanaikaisesti. Pelin tavoitteena on saada mahdollisimman monta tetristä.
Ensimmäinen lauta näyttää esimerkkiasetelman palikoista. Kun I-palikka on pudotettu $8$. sarakkeeseen, se alkaa pudota toisessa ja kolmannessa laudassa esitetyllä tavalla. Sen jälkeen alimmat neljä riviä katoavat, jolloin syntyy tetris ja päädytään neljänteen lautaan.
Kilpailuhenkisenä pienenä kääpiönä Franek haluaa saavuttaa maksimipistemäärän! Hän ei kuitenkaan ole riittävän hyvä pelissä, joten sinun täytyy auttaa häntä. Kun tiedät palikoiden järjestyksen etukäteen, auta Franekia määrittämään suurin mahdollinen tetristen määrä, jonka hän voi saavuttaa pelaamalla optimaalisesti. Anna lisäksi siirtosarja, jolla tämä pistemäärä saavutetaan.
Syöte
Ensimmäinen rivi sisältää yhden kokonaisluvun $N$, palikoiden lukumäärän. Toinen rivi sisältää pituutta $N$ olevan merkkijonon, joka koostuu vain merkeistä I ja O ja kuvaa palikoiden järjestyksen ensimmäisestä viimeiseen.
Tuloste
Tulosta ensimmäiselle riville yksi kokonaisluku, joka on suurin mahdollinen Franekin saavuttama tetristen määrä. Tulosta toiselle riville $N$ kokonaisluvun jono $c_1, c_2, \dots, c_N$, missä $c_i$ on sarake, johon $i$-s palikka tulee pudottaa ($1$-indeksoituna). I-palikalle luvun $c_i$ on toteutettava ehto $1 \le c_i \le 10$. O-palikalle $c_i$ tarkoittaa sen vasemmanpuoleista saraketta ja sen on toteutettava ehto $1 \le c_i \le 9$.
Jos optimaalisia jonoja on useita, voit tulostaa minkä tahansa niistä.
Rajoitukset
$1 \le N \le 200\,000$.
Esimerkit
Syöte 1
10 IIOIOIOOII
Tuloste 1
1 1 2 3 5 3 6 7 7 9 10
Huomautus
Näytetty tuloste on vain yksi kelvollinen siirtosarja; muutkin sarjat voivat saavuttaa saman suurimman mahdollisen tetristen määrän.