Məsələlər
Алфавитный указатель
Алфавитный указатель
Документы текстовых процессоров, в отличии от простых текстовых файлов, содержат помимо текста служебную информацию различного вида. Одним из видов служебной информации являются поля, которые могут описывать вставленные в документ рисунки, формулы, а также управляющую информацию. \textbf{Поля, содержащие управляющую информацию, не видны при просмотре документа в обычном режиме, не учитываются при разбиении на строки и страницы}.
Будем считать, что в документе некого текстового процессора поля описываются следующим образом:
\begin{itemize}
\item поле заключается в фигурные скобки;
\item после открывающейся фигурной скобки следует символ "\textbf{/}";
\item после символа "\textbf{/}" указывается тип поля в виде любого символа, отличного от пробела;
\item вся информация после символа кода поля до закрывающейся фигурной скобки считается текстом поля. Гарантируется, что текст поля не имеет пробелов и состоит, как минимум, из одной буквы;
\item если поле расположено внутри строки, то после него располагается, как минимум, один пробел.
\end{itemize}
Таким образом, признаком начала поля служит комбинация символов "\textbf{\{/}". Например, правильное описание поля может иметь вид: \textbf{\{/AПример\}}.
Одним из видов полей являются поля для формирования алфавитного указателя. Будем считать, что кодом такого поля является символ "\textbf{Z}". Алфавитный указатель представляет собой информацию о встречающихся в документе терминах с указанием номеров страниц, на которых эти термины встречаются.
Алфавитный указатель формируется из полей с кодом "\textbf{Z}" по следующим правилам:
\begin{itemize}
\item все термины сортируются в алфавитном порядке;
\item после термина через пробел указывается номер страницы, на которой он встречается;
\item если термин встречается на нескольких страницах, то страницы выводятся в порядке возрастания через комбинацию символов "запятая+пробел";
\item если термин встречается на странице несколько раз, то для данного термина номер этой страницы указывается только один раз;
\item все термины разбиваются на группы по первому символу. Символ группы выводится перед группой в отдельной строке;
\item большие и маленькие буквы считаются \textbf{различными}.
\end{itemize}
Пример алфавитного указателя:
\textbf{А Арбуз 12, 48 Аспирин 34 П Продавец 73 Я Яблоко 2}
Пусть дан текст, состоящий из слов с вставленными в него полями \textbf{разного типа} (границей слова является пробел, начало и конец строки). Считается, что поле расположено на той же странице, что ближайшее, расположенное перед ним, слово.
Требуется разбить заданный текст на строки и страницы по следующему правилу:
\begin{itemize}
\item строка включает не более \textbf{S} символов, разбиение осуществляется по границам слов, в строке должно быть как можно больше слов, пробелы в начале и конце строки удаляются, между словами должно быть ровно по одному пробелу;
\item страница содержит \textbf{N} строк, пустых строк не может быть;
\item поля считаются \textbf{невидимыми}, т.е. при разбиении текста на строки и страницы все поля удаляются,
\end{itemize}
и для полученного текста построить предметный указатель.
\InputFile
Первая строка содержит два целых числа \textbf{S} и \textbf{N}, разделенных пробелом -- максимальное количество символов в строке и количество строк на странице, соответственно (\textbf{10} ≤ \textbf{S} ≤ \textbf{100}, \textbf{1} ≤ \textbf{N} ≤ \textbf{100}).
Последующие строки содержат исходный текст. Количество строк текста не более \textbf{1000}. Длина строки не более\textbf{200}. Гарантируется, что в отформатированном тексте нет слов, имеющих длину более \textbf{S}. Гарантируется, что перед первым полем есть хотя бы одно слово. Гарантируется, что в тексте есть хотя бы одно поле с кодом "\textbf{Z}".
\OutputFile
Выходной файл должен содержать алфавитный указатель, сформированный по указанным выше правилам.
\Note
После разбиения исходного текста на строки и страницы он будет иметь вид:
Это пример к 1 страница
задаче
"Алфавитный 2 страница
указатель", на
основе которого 3 страница
показывается
построение 4 страница
алфавитного
указателя. 5 страница
Giriş verilənləri #1
15 2 ��� ������{/Z������} � ����� "��������� ��������",{/Z��������} �� ������ �������� ���������� ���������� ����������� ��������.{/Z��������}
Çıxış verilənləri #1
� ������ 1 � �������� 2, 5