Parola

parola

== include(page="template/taskheader" task_id="parola") ==

Fane Babanu incearca sa apare Iasiul si concurentii de la ACM de un nou atac. Cum vremurile s-au schimbat atacul este electronic de aceasta data. Pentru a putea apara Iasiul Fane trebuie sa sparga o parola. Dupa indelungi eforturi el a reusit sa afle ca parola este un text scris cu litere mici in alfabetul latin 'a'-'z', pentru care suma codurilor ascii % $N$ este egala cu $K$. Fane a reusit sa obtina si un text si stie ca parola se afla in acel text dar nu stie intre care pozitii. Pentru a putea gasi parola el va putea folosi oricati plăieşi care vor încerca fiecare o parolă în acelasi timp, totuşi el vrea să reducă numărul de plăieşi folositi la minim. Ajutati-l pe Stefan spunandu-i cate parole se gasesc in textul dat. Fane are de spart maxim $T$ parole.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $parola.in$ are pe prima linie $T$ numarul de parole. Urmeaza $T$ teste fiecare pe $2$ randuri. Pe primul rand a unui test se vor afla $N$ si $K$ pe urmatorul aflandu-se textul.

Fişierul de intrare $parola.in$ ...

h2. Date de ieşire

În fişierul de ieşire $parola.out$, pentru fiecare test pe un rand se va afla un numar reprezentand numarul de parole posibile in fiecare din teste.

În fişierul de ieşire $parola.out$ ...

h2. Restricţii si observatii

h2. Restricţii

* $1 ≤ T ≤ 15$
* $1 ≤ N ≤ 1000000$
* $0 &le; K < N$
* $1 &le; L(text) &le; 1000000$
 
Doua parole vor fi considerate distincte daca sunt intre doi indici diferiti!
Parola vida nu este considerata o parola valida.

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

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

| 2
195 0
abc
196 0
bacbxxbbxxbbb
| 1
5

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

|
h3. Explicaţie

In primul test singura solutie este ab
In al doilea test solutiile sunt bacb, ac, bb(6-7), bb(10-11), bb(11-12)

...

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