jocs

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

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 a 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 \cdot 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$ reprezentând capetele subsecvenţei.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $1 \leq K \leq N$
• $1 \leq T \leq 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

Exemplul 1

jocs.in

2
18 1
atasarapavamefgefg
18 2
atasarapavamefgefg

jocs.out

7
1 1
5
13 15

Explicație

Pentru primul caz, litera a apare de $6$ ori in șir, răspunsul fiind $6 + 1 = 7$
Pentru al doilea caz, șirul efg apare de $2$ ori, răspunsul fiind $2 + 3 = 5$