Talharie

talharie

== include(page="template/taskheader" task_id="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.

Poveste si cerinta...

h2. 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.

Fisierul de intrare $talharie.in$ ...

h2. 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.

In fisierul de iesire $talharie.out$ ...

h2. Restrictii

* $1 ≤ T ≤ 10$
* $1 ≤ N ≤ 100000$
* $0 ≤ K ≤ N$
* Un sir {$(x{~1~},x{~2~}...x{~N~})$} este mai mic din punct de vedere lexicografic decat un alt sir {$(y{~1~},y{~2~}...y{~M~})$} daca exista o pozitie $p$ astfel incat {$x{~p~} < y{~p~}$} si {$x{~1~} = y{~1~}$}, {$x{~2~} = y{~2~}$} ... {$x{~p-1~} = y{~p-1~}$}.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. talharie.in |_. talharie.out |

| 2
  4 0 abcd
  4 2 bbaa
| abcd
  aabb

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicatie

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

...

== include(page="template/taskfooter" task_id="talharie") ==

2919