Uolevi on kehittänyt uuden pakkausmenetelmän, jonka avulla voi tallentaa monen merkkijonon pienempään tilaan.

Menetelmä jakaa merkkijonon osiin ja tallentaa jokaisen osan muodossa ks, jossa k on kokonaisluku ja s on merkkijono. Tämä tarkoittaa, että merkkijono s esiintyy k kertaa peräkkäin. Kaikki osat ovat peräkkäin pakatussa merkkijonossa.

Esimerkiksi merkkijonon ABCABCXXXXXXX voi pakata jakamalla sen osiin ABCABC ja XXXXXXX. Osa ABCABC on pakattuna 2ABC ja osa XXXXXXX on pakattuna 7X, joten koko merkkijono on pakattuna 2ABC7X.

Merkkijonon pakkaamiseen on yleensä monia tapoja. Esimerkiksi merkkijonon ABABAB voi esittää pakattuna 3AB, 1AB2AB, 1A1B1A1B1A1B ja monilla muilla tavoilla. Pakattu merkkijono voi siis olla myös pidempi kuin alkuperäinen merkkijono.

Sinulle annetaan pakattu merkkijono ja tehtäväsi on palauttaa siitä alkuperäinen merkkijono.

Syöte

Syötteen ainoalla rivillä on pakattu merkkijono. Sitä vastaa alkuperäinen merkkijono, jonka pituus on n ja joka muodostuu merkeistä A–Z.

Tuloste

Tulosta alkuperäinen merkkijono.

Esimerkki 1

Syöte:

2ABC7X

Tuloste:

ABCABCXXXXXXX

Esimerkki 2

Syöte:

12A

Tuloste:

AAAAAAAAAAAA

Osatehtävä 1 (18 pistettä)

• 1 \le n \le 20

Osatehtävä 2 (23 pistettä)

• 1 \le n \le 1000

Osatehtävä 3 (59 pistettä)

• 1 \le n \le 10^6