Алфавитный указатель

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

Будем считать, что в документе некого текстового процессора поля описываются следующим образом:

• поле заключается в фигурные скобки;

• после открывающейся фигурной скобки следует символ "/";

• после символа "/" указывается тип поля в виде любого символа, отличного от пробела;

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

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

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

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

Алфавитный указатель формируется из полей с кодом "Z" по следующим правилам:

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

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

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

• если термин встречается на странице несколько раз, то для данного термина номер этой страницы указывается только один раз;

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

• большие и маленькие буквы считаются различными.

Пример алфавитного указателя:

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

Пусть дан текст, состоящий из слов с вставленными в него полями разного типа (границей слова является пробел, начало и конец строки). Считается, что поле расположено на той же странице, что ближайшее, расположенное перед ним, слово.

Требуется разбить заданный текст на строки и страницы по следующему правилу:

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

• страница содержит N строк, пустых строк не может быть;

• поля считаются невидимыми, т.е. при разбиении текста на строки и страницы все поля удаляются,

и для полученного текста построить предметный указатель.

Входные данные

Первая строка содержит два целых числа S и N, разделенных пробелом – максимальное количество символов в строке и количество строк на странице, соответственно (10 ≤ S ≤ 100, 1 ≤ N ≤ 100).

Последующие строки содержат исходный текст. Количество строк текста не более 1000. Длина строки не более200. Гарантируется, что в отформатированном тексте нет слов, имеющих длину более S. Гарантируется, что перед первым полем есть хотя бы одно слово. Гарантируется, что в тексте есть хотя бы одно поле с кодом "Z".

Выходные данные

Выходной файл должен содержать алфавитный указатель, сформированный по указанным выше правилам.

Примеры

Примечание

После разбиения исходного текста на строки и страницы он будет иметь вид:

Это пример к 1 страница

задаче

"Алфавитный 2 страница

указатель", на

основе которого 3 страница

показывается

построение 4 страница

алфавитного

указателя. 5 страница