Алфавітний покажчик

Документи текстових процесорів, на відміну від простих текстових файлів, містять не лише текст, а й різноманітну службову інформацію. Одним із видів такої інформації є поля, які можуть описувати вставлені в документ малюнки, формули, а також керуючу інформацію. Поля з керуючою інформацією не відображаються при перегляді документа у звичайному режимі та не враховуються при розбитті на рядки та сторінки.

Вважатимемо, що в документі певного текстового процесора поля описуються наступним чином:

• поле укладається у фігурні дужки;

• після відкриваючої фігурної дужки йде символ "/";

• після символу "/" вказується тип поля у вигляді будь-якого символу, відмінного від пробілу;

• вся інформація після символу коду поля до закриваючої фігурної дужки вважається текстом поля. Гарантується, що текст поля не містить пробілів і складається щонайменше з однієї літери;

• якщо поле розташоване всередині рядка, то після нього розташовується щонайменше один пробіл.

Таким чином, ознакою початку поля є комбінація символів "{/". Наприклад, правильний опис поля може виглядати так: {/AПриклад}.

Одним із видів полів є поля для формування алфавітного покажчика. Вважатимемо, що кодом такого поля є символ "Z". Алфавітний покажчик містить інформацію про терміни, що зустрічаються в документі, із зазначенням номерів сторінок, на яких ці терміни зустрічаються.

Алфавітний покажчик формується з полів з кодом "Z" за такими правилами:

• всі терміни сортуються в алфавітному порядку;

• після терміна через пробіл вказується номер сторінки, на якій він зустрічається;

• якщо термін зустрічається на декількох сторінках, то сторінки вказуються в порядку зростання через комбінацію символів "кома+пробіл";

• якщо термін зустрічається на сторінці кілька разів, то для цього терміна номер цієї сторінки вказується лише один раз;

• всі терміни розбиваються на групи за першим символом. Символ групи виводиться перед групою в окремому рядку;

• великі та маленькі літери вважаються різними.

Приклад алфавітного покажчика:

ААрбуз 12, 48Аспірин 34ППродавець 73ЯЯблуко 2

Нехай дано текст, що складається зі слів з вставленими в нього полями різного типу (межа слова — пробіл, початок і кінець рядка). Вважається, що поле розташоване на тій же сторінці, що й найближче розташоване перед ним слово.

Потрібно розбити заданий текст на рядки і сторінки за такими правилами:

• рядок включає не більше $S$ символів, розбиття здійснюється за межами слів, у рядку має бути якомога більше слів, пробіли на початку і в кінці рядка видаляються, між словами має бути рівно по одному пробілу;

• сторінка містить $N$ рядків, порожніх рядків не може бути;

• поля вважаються невидимими, тобто при розбитті тексту на рядки і сторінки всі поля видаляються,

і для отриманого тексту побудувати предметний покажчик.