Fişierul intrare/ieşire:	vip.in, vip.out	Sursă	ONI 2019, clasa a 10-a, ziua 2
Autor	Eugenie Daniel Posdarascu	Adăugată de	Tinca Matei •TincaMatei
Timp execuţie pe test	0.75 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Vip

Două personaje ale căror nume se vor da în datele de intrare (momentan îi numim Bossanip si Dicsi) îşi petrec nopţile prin discoteci. Toată lumea ştie că Bossanip este membru V.I.P. în toate discotecile din lume şi Dicsi profită mereu de celebritatea prietenului său. Ajuns pe meleaguri străine, Dicsi s-a confruntat cu o problemă foarte mare. Cum intră la V.I.P. când este pe cont propriu? Astfel, Dicsi s-a apucat de infracţiuni precum furtul de identitate. Dicsi doreşte să permute literele din numele lui (să găsească o anagramă a propriului nume) astfel încât noul nume să difere prin exact K poziţii de numele lui Bossanip. Mai mult, doreşte ca această anagramă să fie minimă lexicografic. Dacă reuşeşte, este posibil să se dea drept Bossanip şi să intre şi el ca membru V.I.P.

Date de intrare

În fişierul text vip.in pe prima linie se află numărul natural T. Pe următoarele 3 * T linii sunt descrise T seturi de date de intrare, fiecare set ocupă câte 3 linii astfel: pe prima linie a unui set se află scrise două numere N (lungimea numelor reale ale lui Bossanip şi Dicsi) şi K; pe a doua linie a unui set este scris numele lui Bossanip dat printr-un şir de caractere s₁; pe a treia linie a unui set este scris numele lui Dicsi dat printr-un şir de caractere s₂. Din fericire pentru Dicsi, cele două personaje au nume de aceeaşi lungime.

Date de ieşire

În fişierul text vip.out se vor scrie, pe fiecare din cele T linii câte un şir de caractere, pe a j-a linie este scrisă anagrama corespunzătoare testului j (noul nume al lui Dicsi) sau -1 dacă nu există o astfel de anagramă.

Restricţii

• 1 ≤ N, K ≤ 10⁵
• Suma valorilor lui N din cadrul seturilor de test ≤ 10⁶
• Toate literele sunt litere mici ale alfabetului englez
• Dacă nu există soluţie pentru un test, atunci se va afişa valoarea -1
• Un şir p₁, p₂, ..., p_N este mai mic lexicografic decât alt şir q₁, q₂, ..., q_N, dacă există o poziţie i, 1 ≤ i ≤ N, astfel încât p_i < p_i şi p_j = q_j, pentru orice j, 1 ≤ j < i
• Pentru 25% din punctaj se poate afişa orice soluţie corectă care nu este neapărat minimă lexicografic

Exemplu

Explicaţie

În primul set cea mai mică anagramă a şirului vasilica, din punct de vedere lexicografic, care diferă de şirul corleone pe exact 6 poziţii, este caliisv.

În al doilea set nici una din anagramele şirului ghita nu poate să difere pe exact două poziţii de şirul marko.

Cum se trimit solutii?