Robotti on rakennuksessa, jossa on n vierekkäistä huonetta. Jokaisen kahden vierekkäisen huoneen välissä on ovi. Joissakin huoneissa on kolikko.

Robotti siirtyy aina lähimpään huoneeseen, jossa on kolikko, ja poimii kolikon. Robotti pysähtyy, kun kaikki kolikot on kerätty tai lähin huone ei ole yksiselitteinen. Jälkimmäisessä tapauksessa robotti ei tiedä, miten sen tulisi toimia.

Montako askelta robotti liikkuu yhteensä ja montako kolikkoa se kerää?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: huoneiden määrä.

Seuraavalla rivillä on merkkijono, jossa on n merkkiä. Merkkijono kuvaa rakennuksen: . on tyhjä huone, * on kolikkohuone ja R on robotin aloitushuone. Merkki R esiintyy tarkalleen kerran.

Tuloste

Tulosta kaksi kokonaislukua: robotin askelten määrä ja kerättyjen kolikoiden määrä.

Esimerkki

Syöte:

20
**.*......*.R*...*..

Tuloste:

4 2

Selitys: Robotti liikkuu ensin askeleen oikealle ja kerää kolikon. Sitten se liikkuu kolme askelta vasemmalle ja kerää kolikon. Tämän jälkeen vasen ja oikea kolikko ovat yhtä kaukana ja robotti pysähtyy.

Kuvassa on esitetty robotin sijainti eri vaiheissa.

Osatehtävä 1 (30 pistettä)

• 1 \le n \le 1000

Osatehtävä 2 (70 pistettä)

• 1 \le n \le 2 \cdot 10^5