Fişierul intrare/ieşire:talharie.in, talharie.outSursăpreONI 2008, Runda finala
AutorAndrei GrigoreanAdăugată dewefgefAndrei Grigorean wefgef
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.
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 (x1,x2...xN) este mai mic din punct de vedere lexicografic decat un alt sir (y1,y2...yM) daca exista o pozitie p astfel incat xp < yp si x1 = y1, x2 = y2 ... xp-1 = yp-1.

Exemplu

talharie.intalharie.out
2
4 0 abcd
4 2 bbaa
abcd
aabb

Explicatie

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content