Dr. Astro Insky lucrează la un centru de radiotelescoape. Recent, a observat o emisie pulsantă de microunde foarte curioasă, trimisă direct din centrul galaxiei. Este emisia transmisă de o formă extraterestră de viață inteligentă? Sau nu este altceva decât bătăile obișnuite ale inimii stelelor?

Cerința

Trebuie să-l ajutați pe Dr. Insky să afle adevărul, oferindu-i un instrument pentru a analiza tiparele de biți din fișierele pe care le înregistrează. Dr. Insky dorește să găsească tiparele de lungime între A și B care se repetă cel mai des în fișierul de date al fiecărei zile. În fiecare caz, se caută cele mai frecvente N tipare distincte. Aparițiile tiparelor se pot suprapune și sunt luate în considerare doar tiparele care apar cel puțin o dată.

Date de intrare

Fișierul de intrare contact.in conține:

• pe prima linie – întregul A care indică lungimea minimă a modelului.
• pe a doua linie – întregul B care indică lungimea maximă a modelului.
• pe a treia linie – întregul N care indică numărul de frecvențe distincte.
• pe a patra linie – o secvență de caractere 0 și 1, fără spații.

Date de ieșire

Fișierul de ieșire contact.out va conține cel mult N linii, care afișează cele mai mari frecvențe și modelele corespunzătoare. Listarea trebuie produsă în ordinea descrescătoare a frecvenței modelului și constă din linii formatate astfel:

frecvență model model ... model

unde frecvența este numărul de apariții ale modelelor care urmează. Modelele de pe fiecare linie trebuie să apară în ordinea descrescătoare a lungimilor. Modelele având aceeași lungime vor fi afișate în ordine invers lexicografică. În cazul în care există mai puțin de N frecvențe distincte, ieșirea va avea mai puțin de N linii.

Restricții și precizări

• 1 ≤ N ≤ 20
• 1 ≤ A ≤ B ≤ 12
• șirul binar are lungimea cel mult 2.500.000

Exemplu:

contact.in

2
4
10
01010010010001000111101100001010011001111000010010011110010000000

contact.out

23 00
15 10 01
12 100
11 001 000 11
10 010
8 0100
7 1001 0010
6 0000 111
5 1000 110 011
4 1100 0011 0001

Explicații:

Se observă de exemplu la linia 5 1000 110 011 în care se afișează modelele de lungime 5. Se tipărește mai întâi modelul de lungime 4 (1000), apoi cele două modele de lungime 3 în ordinea 110 011 deoarece modelul 110 este mai mare lexicografic decât 011.