Annettuna on merkkijono, joka koostuu kirjaimista a–z ja numeroista 1–9.

Seuraavaa operaatiota toistetaan niin kauan kuin merkkijonossa on numeroita jäljellä:

Etsitään merkkijonon vasemmanpuoleisin numero, 1 \le d \le 9. Arvosta riippuen, numeron oikealla puolella oleva d:n pituinen osajono monistetaan. Tämän jälkeen numero poistetaan merkkijonosta.

Esimerkiksi merkkijonolle 82silisko operaatiot etenevät seuraavasti:

82silisko \rightarrow 2silisko2silisko \rightarrow sisilisko2silisko \rightarrow sisiliskosisilisko

Selvitä, mikä merkkijonon sisältö on operaatioiden jälkeen. Voit olettaa, että merkkijonossa on lopulta pelkkiä kirjaimia.

Syöte

Syötteen ainoalla rivillä on merkkijono, joka koostuu merkeistä a–z ja 1–9.

Jokaisen merkkijonossa esiintyvän numeron d oikealla puolella on vähintään d lisää merkkiä.

Tuloste

Tulosta merkkijonon sisältö operaatioiden jälkeen.

Esimerkki 1

Syöte:

82silisko

Tuloste:

sisiliskosisilisko

Esimerkki 2

Syöte:

mis3si1pi

Tuloste:

mississippi

Osatehtävä 1 (71 pistettä)

• Merkkijonon pituus ennen operaatioita on korkeintaan 20

Osatehtävä 2 (29 pistettä)

• Merkkijonon pituus operaatioiden jälkeen on korkeintaan 5\cdot10^5