Index Generation

Most nonfiction and reference books have an index that helps readers find references to specific terms or concepts. Here is a sample index:

larch, 4, 237, 238, 414
+ Monty Python and, 64, 65, 66
+ planting of, 17
Lenny Kravitz, 50
+ going his way, 53
lumbago, 107
mango
+ Chris Kattan, 380
+ storage of, 87, 90
+ use in Nethack, 500, 501
+ Vitamin C content, 192

Each index entry consists of a primary entry followed by zero or more secondary entries, each of which begins with a +. An entry is normally followed by a list of page references, but a primary entry may have none if it has at least one secondary entry (as with mango above). Primary entries are sorted, and the secondary entries under a primary entry are also sorted. Sorting is case-insensitive. The page references for an entry are listed in ascending order with no duplicates. (A duplicate could occur if two or more identical entries appear on the same page.)

Your task is to read a document that has index information embedded in it and produce the index. A document consists of one or more lines of ASCII text. The page number starts at 1, and the character & marks the start of a new page (it adds 1 to the current page number). Index entries are indicated by a marker. In its most elaborate form a marker has the following syntax:

{text%primary$secondary}

Here text is the text being indexed, primary is an alternative primary entry, and secondary is a secondary entry. Both %primary and $secondary are optional, but if both are present they must appear in the order shown. If primary is present it is used as the primary entry; otherwise text is used as the primary entry. If secondary is present, the marker adds a page reference for that secondary entry; otherwise it adds a page reference for the primary entry. A single marker cannot add a page reference for both a primary and a secondary entry. Here are examples of each of the four possible marker types, corresponding to four of the entries in the sample index above:

• ... his {lumbago} was acting up, so ...
• ... {Lenny%Lenny Kravitz} lit up the crowd with his version of ...
• ... Monty Python often used the {larch$Monty Python and} in ...
• ... when storing {mangos%mango$storage of}, be sure to ...

The input consists of one or more documents, followed by a line containing only ** that marks the end of the input. Documents are implicitly numbered starting from 1. Each document consists of one or more lines of text followed by a line containing only *. Each line of text is at most 79 characters long, not counting the end-of-line characters.

For document i, output the line DOCUMENT i followed by the sorted index, using the exact output format shown in the example test cases.

Note the following:

• A document contains at most 100 markers, with at most 20 primary entries.
• A primary entry has at most 5 secondary entries.
• An entry has at most 10 unique page references (duplicates are not counted).
• The character & never appears inside a marker, and appears at most 500 times in a document.
• The character * is used only to signal the end of a document or the end of the input.
• The characters {, }, %, and $ are used only to define markers and never appear in ordinary text or in an entry.
• A marker may span one or more lines. Every end-of-line inside a marker is converted to a single space.
• A space inside a marker (including a converted end-of-line) is normally kept as part of the text/entry, just like any other character. However, any space that immediately follows {, immediately precedes }, or is immediately adjacent to % or $ is ignored.
• The total length of a marker, measured from the opening { to the closing } with every embedded end-of-line converted to a space, is at most 79 characters.