Contatto

Il Dr. Astro Insky lavora al centro radiotelescopico. Recentemente, ha notato una curiosa emissione pulsante di microonde dal centro della galassia. Forse l'emissione è trasmessa da qualche forma di vita extraterrestre intelligente... o non è altro che il solito battito cardiaco delle stelle?

Il problema

Dovete aiutare il Dr. Insky a scoprire la verità fornendo uno strumento per analizzare i pattern (sequenze) di bit nei file che vengono registrati. Il Dr. Insky vuole scoprire i pattern di lunghezze comprese tra A and B (inclusi) che si ripetono più spesso nei file registrati ogni giorno. In ognuno dei casi, dovete cercare le massime N frequenze (cioè, numeri di occorrenze) distinte. Le occorrenze di pattern si possono sovrapporre, e solo i pattern che capitano almeno una volta vengono presi in considerazione.

Dati in input

Il file CONTACT.IN contiene la serie di dati nel seguente formato:

Prima riga - L'intero A che indica la minima lunghezza di un pattern.
Seconda riga - L'intero B che indica la massima lunghezza di un pattern.
Terza riga - L'intero N che indica il numero di frequenze distinte.
Quarta riga - Una sequenza di caratteri 0 e 1, terminati da un carattere 2.

Esempio di input

2
4
10
010100100100010001111011000010100110011110000100100111100100000002

In questo caso vengono richieste le massime dieci frequenze di pattern di lunghezza compresa tra due e quattro che occorrono nella sequenza di bit
01010010010001000111101100001010011001111000010010011110010000000.

In questo esempio il pattern 100 occorre 12 volte, e il pattern 1000 5 volte. Il pattern più frequente è 00.

Dati in output

Un file CONTACT.OUT con al più N righe, che lista le N maggiori frequenze e i pattern corrispondenti. La lista deve essere prodotta in ordine decrescente di frequenza, ed è composta da righe nel formato frequenza pattern pattern ... pattern, dove frequenza è il numero di occorrenze dei pattern che seguono. I pattern in ogni riga devono apparire in ordine decrescente di lunghezza. Pattern di uguale lunghezza devono essere elencati in ordine di valore numerico decrescente. Se ci sono meno di N frequenze distinte, la lista in output potrà avere meno di N righe.

Esempio di output

Per l'esempio di input summenzionato, l'output deve essere

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

Vincoli

Il file di input può essere lungo fino a 2 megabyte. I parametri A, B e N sono vincolati come segue:

0 < N <= 20
0 < A <= B <= 12