index

Un editor de texte evoluat trebuie sa includa facilitatea de indexare a documentelor.

Un document este constituit dintr-o succesiune de paragrafe. Un paragraf este constituit din una sau mai multe linii. Paragrafele sunt separate prin exact o linie goala.

În primul rând documentul este paginat, fiecare pagina fiind constituita din maxim n linii. Liniile sunt plasate în pagina în ordinea în care apar în document, pâna când pagina "se umple" (contine n linii), respectând în acelasi timp si urmatoarele reguli de formatare:
1. Daca ultima linie a unei pagini este ultima linie a unui paragraf, atunci urmatoarea linie goala este eliminata (adica pagina urmatoare nu va începe cu linie goala, ci cu prima linie din paragraful urmator).
2. Daca ultima linie a unei pagini este prima linie a unui paragraf care contine mai mult de o linie (aceasta linie este denumita în tehnoredactare linie orphan), atunci aceasta linie este mutata pe pagina urmatoare.
3. Daca ultima linie a unei pagini este penultima linie a unui paragraf care contine mai mult de 3 linii, atunci aceasta linie este mutata pe ultima linie (în caz contrar ultima linie a paragrafului ar fi prima linie de pe pagina urmatoare, ceea ce în tehnoredactare este denumita linie widow).
4. Daca ultima linie de pe pagina este penultima linie a unui paragraf care contine doua sau trei linii, atunci întregul paragraf este mutat pe pagina urmatoar (evitând în acest fel sa obtinem atât linie orphan cât si linie widow) .
Regulile de paginare sunt aplicate în ordine, de la începutul documentului, pagina cu pagina.

Consideram cuvânt o succesiune de litere din alfabetul englez (nu se va face distinctie între literele mici si literele mari).

Un index este lista strict ordonata lexicografic a tuturor cuvintelor care apar în document si a numerelor de pagina la care apar aceste cuvinte. Numerele de pagina la care apare fiecare cuvânt trebuie sa fie specificate în ordine crescatoare, si vor fi separate prin virgula. Daca un cuvânt apare pe trei sau mai multe pagini consecutive, atunci se specifica doar numarul primei pagini si numarul ultimei pagini dintre acestea, separate prin liniuta (caracterul '-').
De exemplu:
MUSEUM 3-5,7-10,12,18,22-29

Cerință
Date fiind numarul de linii din pagina si documentul să se determine indexul.

Date de intrare
Fișierul de intrare index.in conține pe prima linie un număr natural nenul n, reprezentând numarul maxim de linii care pot fi plasate într-o pagina. Pe urmatoarele linii este scris documentul care trebuie sa fie indexat.

Date de ieșire
Fișierul de ieșire index.out va conține mai multe linii, câte una pentru fiecare cuvânt din document.
Fiecare linie va contine un cuvânt urmat de un singur spatiu si apoi de lista numerelor de pagina la care apare cuvântul, formatata ca în enunt. Cuvintele vor fi specificate în ordine strict lexicografica si vor fi scrise cu majuscule.

Restricții și precizări
4<=n<=100
Dimensiunea documentului care trebuie sa fie indexat nu depaseste 20 000 bytes.
Liniile din document nu încep si nici nu se termina cu spatii.
Documentul nu va contine doua linii goale consecutive.
Prima linie a documentului nu este goala.
Lungimea unei linii nu depaseste 200 de caractere.

Exemplu

index.in index.out

5
Din anul 2002 mii de elevi participa
la programul de pregatire de performanta in informatica .campion.
In fiecare an cel putin 10 elevi de la fiecare grupa participa
la finala .campion

cei mai buni se intrec cu cei mai buni

.campion se adreseaza tuturor celor pentru care performanta

reprezinta o pasiune, celor pentru care rezolvarea
unei probleme este o bucurie

celor impatimiti de jocurile mintii

an de an cei care au fost elevi devin profesori
se alatura echipei .campion
pentru a insufla mai departe pasiunea pentru performanta in informatica
celor ce le calca pe urme

celor ce urmeaza sa fie cel putin la fel de buni
pe cat au fost si ei

.campion e super!
participa si tu la .campion!
alatura-te celor mai buni!

 A 4
ADRESEAZA 2
ALATURA 4,6
AN 1,4
ANUL 1
AU 4,5
BUCURIE 3
BUNI 2,5,6
CALCA 4
CAMPION 1,2,4,6
CARE 2-4
CAT 5
CE 4,5
CEI 2,4
CEL 1,5
CELOR 2-6
CU 2
DE 1,3-5
DEPARTE 4
DEVIN 4
DIN 1
E 6
ECHIPEI 4
EI 5
ELEVI 1,4
ESTE 3
FEL 5
FIE 5
FIECARE 1
FINALA 1
FOST 4,5
GRUPA 1
IMPATIMITI 3
IN 1,4
INFORMATICA 1,4
INSUFLA 4
INTREC 2
JOCURILE 3
LA 1,5,6
LE 4
MAI 2,4,6
MII 1
MINTII 3
O 3
PARTICIPA 1,6
PASIUNE 3
PASIUNEA 4
PE 4,5
PENTRU 2-4
PERFORMANTA 1,2,4
PREGATIRE 1
PROBLEME 3
PROFESORI 4
PROGRAMUL 1
PUTIN 1,5
REPREZINTA 3
REZOLVAREA 3
SA 5
SE 2,4
SI 5,6
SUPER 6
TE 6
TU 6
TUTUROR 2
UNEI 3
URME 4
URMEAZA 5

Timp maxim de execuție/test: 0.5 secunde
Memorie totala disponibila: 48 Mb, din care 16 Mb pentru stiva.

prof. Emanuela Cerchez
Liceul de Informatică "Gr. C. Moisil" Iași
emanuela.cerchez@gmail.com