Vzrušujúce noviny! V auguste sa bude konať veľkolepá lingvistická konferencia v Memphis v Tennessee. A pozvaní sú všetci! Budú aj prednášky. Prednášku bude mať napríklad Viktor. O čom? Isto ste počuli o významných objavoch nekrolingvistky Kristíny. Minulé kolo sa jej podarilo ukázať, že isté prastaré atlantídske zvitky sú z neznámych socio-kultúrnych dôvodov napísané tak, aby obsahovali palindrómy1… Ale čo to môže znamenať? Odkiaľ pramení táto atlantídska fascinácia palindrómami? Viktor si myslí, že zistil odpoveď. Na jednom zvitku totiž našiel niečo takéto:
Pokiaľ sa Viktor nemýli, jedná sa o historicky vôbec prvé vyobrazenie obrovskej kozmickej ploštice (pohľad zvrchu). Určite sa pýtate “?”. Všetko pochopíte, až budete starší, približne presne o pár sekúnd. Predstavte si, že ste atlantíďan. Keď za vami takáto kozmická ploštica príde, naskytne sa vám približne nasledovný pohľad (kozmická ploštica spredu - be not afraid):
Ale čo! Vidíte to aj vy? Táto kozmická ploštica vyzerá úplne ako palindróm (os súmernosti je vyznačená)!!! Viktor verí, že prví atlantíďania nadizajnovali svoje písmo podľa ploštičej tváre, a aj potom, čo kozmické ploštice vymreli2, sa moderný skript snaží túto spomienku zachovať už spomínaným spôsobom písania3.
Ale čo s týmto zistením? Samozrejme, treba zrekonštruovať, ako mohli kozmické ploštice naozaj vyzerať! Vpred-smerujúca kozmická ploštica na obrázku vyššie je totiž iba estimácia. Naviac, každá kozmická ploštica je unikátna.
Vieme, že prvé atlantídske vety vznikli z ploštičej tváre, ktorú atlantíďania rozdelili na jednotlivé slovíčka. Teda rekonštrukcia je jednoduchá: vezmeme slovíčka, ktoré poznáme, a vyskladáme z nich našu predstavu ploštičej tváre…
Úloha
Na vstupe dostanete niekoľko reťazcov pozostávajúcich z malých písmen anglickej abecedy. Vašou úlohou je na výstup vypísať ľubovoľný palindróm, ktorý vie vzniknúť tak, že niektoré zo vstupných reťazcov v nejakom poradí zapíšeme priamo za seba (môžu sa aj opakovať, a nemusíte použiť všetky), prípadne zistiť, že sa to nedá.
Formát vstupu
V prvom riadku vstupu je číslo \(n\) udávajúce počet slov, ktoré poznáme.
Na každom z \(n\) nasledovných riadkov je jedno slovo – reťazec dĺžky \(d_i\) (\(1 \leq d_i \leq 10\)) pozostávajúci z malých písmen anglickej abecedy. Navyše platí, že žiadne slovo nie je prefixom ani suffixom iného, teda zo žiadneho slova nevieme dostať žiadne iné iba tak, že na jeho začiatok alebo koniec pridáme nejaké znaky.
Počty slov sú v jednotlivých sadách nasledovné:
| Sada | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| \(1 \leq n \leq\) | \(10\) | \(1\,000\) | \(30\,000\) | \(40\,000\) |
Formát výstupu
Na jedinom riadku výstupu vypíšte palindróm pozostávajúci z malých písmen anglickej abecedy, ktorý sa dá zo vstupných slov vyskladať. Ak ich existuje viac, vypíšte ľubovoľný z nich. Ak neexistuje žiaden, vypíšte -1.
Príklady
Input:
5
jelenovi
ani
sobovi
nelej
pivoOutput:
jelenovipivonelejInput:
3
takyto
palindrom
neexistujeOutput:
-1Input:
2
aktivi
tkaOutput:
aktivitkapalindróm je taký reťazec, že odzadu sa číta rovnako ako odpredu, teda napríklad “aktivitka”. Vedúci KSP palindrómy zbožňujú a majú ich každé raňajky.↩︎
momentálne asi vedeckou komunitou najuznávanejšia teória je, že kozmické ploštice nezmizli, len sa vplyvom gravitácie z plochého tvaru zaguľatili a do dnešného dňa prežívajú v podobe basketbalových lôpt.↩︎
azda atlantíďania verili, že kozmické ploštice sa ku nim vrátia, pokiaľ sa text bude opäť na ich podobizeň podobať?↩︎
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.