Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš, koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a, skús sa pozrieť ako by mal vyzerať ideálny program. Ak zatiaľ programovať nevieš, ale chcel/a by si sa naučiť, môžeš skúsiť našu KSP School.
Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Kubovi ([email protected]) alebo Ivke ([email protected]).
Dobrodruh Štepi sa rozhodol ísť na výpravu. Nechcel ísť sám, tak zo sebou zobral kuchárku Mišku, aby nehladovali. No a aby sa nenudili, išla s nimi aj papagáj Hanka. Nachystali sa, zbalili kopu vecí, veľa jedla, a vyrazili. Zopár dní sa túlali po pralesoch, keď zistili, že sa im míňajú zásoby jedla. Hanka vyletela nad stromy a v diaľke zbadala dedinu. Vydali sa smerom k nej a dúfali, že miestni budú priateľskí.
V dedine do ktorej Štepi dorazil mal však problém. Nevedel, ako komunikovať s domorodcami. Domorodci používajú zvláštny jazyk, v ktorom sa každá veta skladá z rôznej množiny znakov bez medzier. Aby to nebolo dosť zvláštne, vedia ich vnímať iba ak sú v podobe palindrómov. Ak by im Štepi povedal niečo čo nie je palindróm, začali by sa naňho ozaj škaredo a nechápavo pozerať a to on nerád.
Štepi by s nimi chcel vedieť komunikovať, no sám to nezvládne, nakoľko má žiaľ aibofóbiu (fóbiu z palindrómov). Potreboval by preto od teba pomoc s komunikáciou s domorodcami.
Štepi by chcel domorodcom povedať $T$ viet, pre ktoré už má množiny znakov priparvené. Od teba potrebuje, aby si ich naformuloval/a do palindrómov. Je však možné, že urobil chybu, a v tom prípade sa palindróm vytvoriť nedá. Ak na takú vetu narazíš, daj mu vedieť.
Na prvom riadku dostaneš jedno číslo $T$ ($1 \leq T \leq 2000$) označujúce počet viet, ktoré Štepi potrebuje naformulovať. Nasleduje $T$ dvojíc riadkov. Na prvom riadku z dvojice je číslo $1 \leq N \leq 10^5$ udávajúce počet znakov vo vete a na druhom riadku z dvojice je nenaformulovaná veta, skladajúca sa z $N$ znakov malej anglickej abecedy.
Exituje 5 sád vstupov, každá za 20 bodov. V jednotlivých sadách platia nasledovné obmedzenia:
| Sada | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| $1 \leq T \leq$ | $10$ | $50$ | $500$ | $2000$ | $50$ |
| $1 \leq N \leq$ | $10$ | $50$ | $200$ | $2000$ | $10^5$ |
Pre každú vetu vypíšte na zvlášť riadok jej formuláciu v podobe palindróm, prípadne
ak sa nedá naformulovať do podoby palidnrómu, vypíšte CHYBA.
Ak existuje viacero spôsobov naformulovania vety, vypíšte ľobovoľný z nich.
5
5
abbaa
4
abbb
6
zxyxxz
10
apkrrsapsk
11
mpfsxkmskpf
ababa
CHYBA
CHYBA
praskksarp
fkmspxpsmkf
Prvú vetu by sme mohli naformulovať napr. aj ako baaab. Podobne to platí aj pre
ostatné vety, ktoré sa dajú naformulovať ako palindróm.