25158번 - Hulja 다국어

Tonči je za rođendan dobio veliku ploču s N redaka i M stupaca popunjenu slovima. Donio ju je Vjekoslavi i rekao: „Evo ploče, a ti smisli tekst.”

Kako bi osmislila tekst, Vjekoslava je na neko polje stavila figuricu te slovo zapisano na tom polju napisala na papir kao početak riječi. Zatim je figuricu određen broj puta pomaknula za jedno polje, uvijek se krećući u nekom od osam smjerova. Dok je pomicala figuricu, na kraj je riječi redom dopisivala sva slova zapisana na poljima koja je figurica posjećivala, pazeći da nikad ne posjeti polje sa slovom koje već ima u riječi.

Vjekoslavin omiljeni broj je D, tako da je pazila i da joj riječ ne premaši duljinu D. Ako u nekom trenutku više nije mogla pomaknuti figuricu, dodavala je slova ‘Z’ na kraj riječi, sve dok joj riječ nije dostigla duljinu D.

Koja je po abecedi najmanja riječ koju je Vjekoslava mogla sastaviti?

U prvom retku nalaze se brojevi N i M (1 ≤ N, M ≤ 1000), brojevi iz teksta zadatka.

U drugom retku nalazi se broj D (1 ≤ D ≤ 26), broj iz teksta zadatka.

U sljedećih N redaka nalazi se po M velikih slova engleske abecede koja predstavljaju Tončijevu ploču.

U jedini redak treba ispisati traženu riječ iz teksta zadatka.