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 succesiune de elemente aflate pe poziţii consecutive) de lungime minimă K, astfel încât numărul de apariţii ale subsecvenţei [i, j] în şirul dat plus j – i + 1 să fie maxim.
Cerinţă
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 ale acestei subsecvenţe în şir plus lungimea acesteia, adică j – i + 1.
Date de intrare
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.
Date de ieşire
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.
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 să 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.
Exemple
jocs.in
jocs.out
Explicaţii
2
18 1
atasarapavamefgefg
18 2
atasarapavamefgefg
7
1 1
5
13 15
Pentru primul caz, litera ′a′ apare de 6 ori in sir, răspunsul fiind 6 + 1 = 7
Pentru al doilea caz, sirul ″efg″ apare de 2 ori, răspunsul fiind 2 + 3 = 5