Cerința

Două personaje ale căror nume se vor da în datele de intrare (momentan îi numim Bossanip și 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 trei linii astfel: pe prima linie a unui set se află scrise două numere naturale 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 s1; pe a treia linie a unui set este scris numele lui Dicsi dat printr-un șir de caractere s2. 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 și precizări

• 1 ≤ N, K ≤ 100.000
• Suma valorilor lui N din cadrul seturilor de test este mai mică sau egală cu 1.000.000
• 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 p1, p2, …, pN este mai mic lexicografic decât un alt șir q1, q2, …, qN, dacă există o poziție i , 1 ≤ i ≤ N, astfel încât pi < qi și pj = qj, 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:

vip.in

2 
8 6 
corleone 
vasilica 
5 2 
marko 
ghita

vip.out

caaliisv 
-1

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 caaliisv În al doilea set nici una din anagramele șirului ghita nu poate să difere pe exact două poziții de șirul marko.