Mario opet izmišlja glupe igre umjesto da čita Dostojevskog za lektiru. Pravila njegove najnovije igre su sljedeća:

Prvo slučajnim odabirom odabere neku riječ iz knjige. Zatim proizvoljno odabere dva mjesta u riječi na kojima će je rastaviti tako da dobije ukupno tri riječi.

Nakon toga u svakoj od tri dobivene riječi obrne poredak slova, tako da se prvo slovo u riječi zamijeni sa zadnjim, drugo s predzadnjim i tako dalje.

Konačno, riječi ponovo spaja u jednu pazeći da zadrže isti međusobni poredak.

Cilj igre je na opisani način dobiti leksikografski što je moguće raniju riječ. Drugim riječima, meñu svim riječima koje je moguće dobiti na opisani način treba odabrati onu koja bi se u rječniku nalazila najranije.

Napišite program koji uspješno igra Marijevu igru.

Ulazni podaci

U prvom retku nalazi se odabrana riječ, niz malih slova engleske abecede (bez razmaka).

Broj znakova u nizu biti će izmeñu \(3\) i \(50\).

Izlazni podaci

U prvi redak potrebno je ispisati traženu riječ.

Primjeri test podataka

Ulaz

dcbagfekjih

Izlaz

abcdefghijk

Ulaz

mobitel

Izlaz

bometil

Ulaz

anakonda

Izlaz

aanadnok