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

Poveste şi cerinţă...

Gauss şi Seidel, plictisiţi de activităţile lor cotidiene, s-au apucat de un nou joc. Fiind dat un şir de $N$ caractere şi un număr $K$, trebuie găsită o subsecvenţă $[i, j]$ a acestuia (adică o submulţime de elemente aflate pe poziţii consecutive) de lungim$e minimă $K$, astfel încât numărul de apariţii a subsecvenţei $[i, j]$ în şirul dat plus $j – i + 1$ să fie maxim.
 
h2. Cerinta
 
Fiind dat un şir de $N$ caractere şi un număr natural $K$, găsiţi pentru acest şir o subsecvenţă cuprinsă între poziţiile $[i, j]$ care maximizează numărul de apariţii a acestei subsecvenţe în şir plus lungimea acesteia, adică $j – i + 1$.

h2. Date de intrare

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

Fişierul de intrare jocs.in conţine pe prima linie un număr natural $T$ reprezentând numărul cazurilor de test. Un test este descris prin două linii. Prima linie conţine numerele $N$ şi $K$ cu semnificaţia de mai sus. Pe a doua linie se află $N$ caractere, reprezentând şirul dat.

h2. Date de ieşire

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

Fisierul de ieşire jocs.out va conţine $2 * T$ linii, reprezentând răspunsurile pentru cele T teste. Un răspuns se scrie pe două linii: pe prima linie se va scrie numărul de apariţii al subsecvenţei găsite plus lungimea sa, iar pe a doua linie numerele $i$ şi $j$ $(i ≤ j)$ reprezentând capetele subsecvenţei.

h2. Restricţii

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

 
* $1 ≤ N ≤ 100 000$
* $1 ≤ K ≤ N$
* $1 ≤ T ≤ 5$
* pentru ca un răspuns sa fie considerat corect, subsecvenţa afişată trebuie sa apară în şirul iniţial de cel puţin 2 ori
* se garantează că pentru fiecare K dat există o soluţie
* în cazul în care există mai multe răspunsuri corecte, puteţi să afişaţi oricare dintre acestea

h2. Exemplu