Andy is fond of old computers. He loves everything about them
and he uses emulators of old operating systems on his modern
computer. Andy also likes writing programs for them. Recently he
has decided to write a text editor for his favorite text-mode operating
system.
The most difficult task he has got stuck with is document indexing.
An index of the document is the lexicographically ordered list of all words occurring in the
document with the numbers of pages they occur at. Andy feels that he
is not able to write the component of the editor that performs
indexing, so he asks you to help.
A document is a sequence of paragraphs. Each paragraph consists
of one or more lines. Paragraphs are separated from each other
with exactly one blank line.
First, the document is paginated — divided into pages.
Each page consists of up to n lines. Lines are placed on the page
one after another, until n lines are placed. The
following correction rules are then applied:
If the last line on a page is the last line of the paragraph,
then the following empty line is skipped, i.e. it is not placed on any
page. Therefore, the page never starts with a blank line.
If the last line on a page is the first line of a paragraph
that contains more than one line (so called orphan line),
then it is moved to the next page.
If the last line on a page is the next-to-last line of a paragraph
that contains more than three lines, then this line is moved to the next page
(otherwise, the last line of the paragraph would be alone
on the page — so called widow line).
If the last line on a page is the next-to-last line of a paragraph
that contains exactly two or three lines, then the whole paragraph is moved to the next page
(so we have neither orphan, nor widow lines).
After applying the correction rules the next page is formed, and so on
until the whole document is paginated.
A word is a continuous sequence of letters of the English alphabet.
Case is not important.
The index of the document contains each word from the document and the
list of the pages it occurs at.
The numbers of pages a word occurs at must
be listed in the ascending order. Numbers must be separated by commas.
If a word occurs on three or more consecutive pages, only the first
and the last page numbers of this range must be listed, separated by a dash,
for example 3-5,7-10,12,13,15.
Input file format
The first line of the input file contains n . The rest of
the input file contains the document to be indexed.
The line is considered blank if it is completely empty.
No line contains leading or trailing spaces.
The document does not contain two consecutive blank lines.
The first line of the document is not blank.
Output file format
Print all words that occur in the given document. Words must be printed
in the lexicographical order, one word on a line.
After each word print one space followed by
the list of pages it occurs at, formatted as described in problem
statement. Use capital letters in output.
Constraints
4 ≤ n ≤ 100.
The size of the input file does not exceed 20000 bytes.
The length of each line of the document does not exceed 200 characters.
Sample tests
No.
Input file (document.in)
Output file (document.out)
1
6
From thousands of teams competing in regional
contests held from September to December 2004
world-wide, seventy-five teams will advance to
the World Finals in Shanghai, April 3-7, 2005.
Awards, prizes, scholarships, and bragging rights
will be at stake for some of the world's finest
university students of the computing science.
Join us for the challenge, camaraderie,
and the fun! Become the best of the best
of the best in ACM ICPC!
ACM ICPC is the best contest!
ACM 3
ADVANCE 1
AND 2,3
APRIL 1
AT 2
AWARDS 2
BE 2
BECOME 3
BEST 3
BRAGGING 2
CAMARADERIE 3
CHALLENGE 3
COMPETING 1
COMPUTING 2
CONTEST 3
CONTESTS 1
DECEMBER 1
FINALS 1
FINEST 2
FIVE 1
FOR 2,3
FROM 1
FUN 3
HELD 1
ICPC 3
IN 1,3
IS 3
JOIN 3
OF 1-3
PRIZES 2
REGIONAL 1
RIGHTS 2
S 2
SCHOLARSHIPS 2
SCIENCE 2
SEPTEMBER 1
SEVENTY 1
SHANGHAI 1
SOME 2
STAKE 2
STUDENTS 2
TEAMS 1
THE 1-3
THOUSANDS 1
TO 1
UNIVERSITY 2
US 3
WIDE 1
WILL 1,2
WORLD 1,2
