Fişierul intrare/ieşire:	talharie.in, talharie.out	Sursă	preONI 2008, Runda finala
Autor	Andrei Grigorean	Adăugată de	Andrei Grigorean •wefgef
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Talharie

Deoarece sunt atatea concerte in aceasta vara, Miruna are nevoie de bani pentru a-si cumpara bilete. Ce alta idee mai buna ar fi putut sa-i vina fetitei decat sa jefuiasca o banca? Zis si facut, iat-o in fata seifului. Dupa ca l-a amenintat cu pistolul la tampla pe directorul bancii, Miruna a reusit sa obtina codul special al seifului. Acesta este un sir cu N caractere ce sunt litere mici ale alfabetului. Lucrurile nu sunt insa atat de simple pe cat par, deoarece pentru a patrunde in camera cu bani codul trebuie descifrat. Miruna stie ca trebuie sa roteasca sirul de caractere cu exact K pozitii spre stanga, iar apoi sa repete acelasi procedeu pana ajunge din nou la sirul initial.

Cerinta

Pentru un sir de N caractere si un numar K, aflati cel mai mic sir din punct de vedere lexicografic pe care il putem obtine din sirul initial operand de mai multe ori rotatii circulare spre stanga cu cate K pozitii.

Date de intrare

Fisierul de intrare talharie.in contine pe prima linie un numar natural T, reprezentand numarul de teste. Urmatoarele T linii vor contine cate doua numere naturale N si K, avand semnficatia din enunt, urmate de un sir de N litere mici ale alfabetului.

Date de iesire

Fisierul talharie.out va contine T linii, pe fiecare linie gasindu-se un sir de caractere reprezentand cel mai mic sir din punct de vedere lexicografic care se poate obtine pentru fiecare test.

Restrictii

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 100000
• 0 ≤ K ≤ N
• Un sir (x₁,x₂...x_N) este mai mic din punct de vedere lexicografic decat un alt sir (y₁,y₂...y_M) daca exista o pozitie p astfel incat x_p < y_p si x₁ = y₁, x₂ = y₂ ... x_p-1 = y_p-1.

Exemplu

Explicatie

Pentru primul test, singurul sir care poate fi obtinut este abcd. Pentru al doilea test putem obtine bbaa sau aabb.

Cum se trimit solutii?