Alphabetical Index#4060
Documents created with word processors, unlike plain text files, include not only text but also various types of metadata. One such type of metadata is fields, which can describe inserted images, formulas, and control information. Fields containing control information are not visible when viewing the document in normal mode and are not considered during line and page breaks.
In a particular word processor, fields are described as follows:
A field is enclosed in curly braces.
After the opening curly brace, there is a symbol "/".
Following the symbol "/", the field type is indicated by any character other than a space.
All information after the field type symbol up to the closing curly brace is considered the field text. It is guaranteed that the field text does not contain spaces and consists of at least one letter.
If the field is located within a line, it is followed by at least one space.
Thus, the start of a field is marked by the symbol combination "{/". For example, a valid field description might look like this: {/AExample}.
One type of field is used for creating an alphabetical index. Let's assume that the code for such a field is the symbol "Z". The alphabetical index contains information about terms that appear in the document, along with the page numbers where these terms are found.
The alphabetical index is created from fields with the code "Z" according to the following rules:
All terms are sorted in alphabetical order.
After each term, the page number where it appears is listed, separated by a space.
If a term appears on multiple pages, the pages are listed in ascending order, separated by "comma+space".
If a term appears multiple times on the same page, the page number is listed only once for that term.
All terms are grouped by their first character. The group symbol is displayed on a separate line before the group.
Uppercase and lowercase letters are considered different.
Example of an alphabetical index:
AArbuz 12, 48Aspirin 34PSeller 73YApple 2
Consider a text consisting of words with inserted fields of different types (word boundaries are spaces, line beginnings, and line endings). It is assumed that a field is located on the same page as the nearest preceding word.
The task is to break the given text into lines and pages according to the following rules:
A line can contain no more than characters. Line breaks occur outside of words, and the line should contain as many words as possible. Spaces at the beginning and end of the line are removed, and there should be exactly one space between words.
A page contains lines, and there cannot be empty lines.
Fields are considered invisible, meaning they are removed when breaking the text into lines and pages.
After formatting the text, construct the index.
The first line contains two integers and , separated by a space — the maximum number of characters per line and the number of lines per page, respectively (10 \leq S \leq 100, 1 \leq N \leq 100).
The following lines contain the source text. The number of text lines is no more than . The length of a line is no more than . It is guaranteed that in the formatted text, there are no words longer than . It is guaranteed that there is at least one word before the first field. It is guaranteed that there is at least one field with the code "Z" in the text.
The output file should contain the alphabetical index formed according to the rules specified above.
Example 1
After breaking the source text into lines and pages, it will look like:
This is an example to 1 page
task
"Alphabetical 2 page
index", on
the basis of which 3 page
shows
the construction 4 page
of the alphabetical
index. 5 page