Mobile Phone industry is the fastest growing industry in Wonderland. The three prominent mobile service providers of Wonderland are Coktel, Anglolink and Grinding Phone. All three operators provide very cheap rate packages after 12:00 AM. The name of their packages are “The Thief Talk” (“Chorer Alap” in Bangla), “Insomnia” and “The Vampire Chat” respectively. These cheap packages have inspired many people to disturb others at Night.

One such gone to ashtray guy is Arif whose activities begin after 12:00 AM. He dials a number randomly and writes down it in his notebook if he likes it. Later he dials those numbers written in his notebook frequently. As names are not important to him so his note book contains only numbers, and no names. But in a few days his notebook becomes filled with many numbers. So now he wants to reorganize the numbers in a new notebook. The reorganizing process is described below:

Arif’s notebook contains many numbers so there may exist some consecutive numbers. Therefore he wants to save space by writing the consecutive numbers as a range. For example if there are three numbers 01711322396, 01711322397, 01711322398 then he will write them as 01711322396-8. It means that the smallest number in the sequence is the first part of the range followed by a hyphen and then only the rightmost digits of the largest number that are different than the first number. A phone number can have any numerical value within 100 and 2000000000 (inclusive) and is always preceded by only a single zero. So 01123 is a valid phone number but 00123, 089, 1234, 02000000001 are invalid phone numbers.

You will be given up to 100000 sorted phone (As you can’t sort numbers) numbers and your job is to write a program that does the job for Arif. 

Input

The input file contains 110 sets of inputs. But only about 10% of them are large inputs. The description of each set is given below:

Each set starts with an integer N (0 ≤ N ≤ 100000) which denotes how many phone numbers are there in this set. Each of the next N lines contains a valid phone number. The phone numbers will be sorted in ascending order according to their numerical values. You can assume that all input phone numbers will be valid and distinct. You can also assume that all phone numbers in a single set will have equal length.

Input is terminated by a set where the value of N=0. This set need not be processed.

Output

For each set of inputs produce two or more lines of outputs. The description of output for each set is given below.

First line contains the serial of output. Next lines contain the phone numbers printed according to the rule mentioned in the problem statement. The numbers which are not part of a consecutive sequence are printed exactly as the input and the consecutive number sequences are printed as range. Print a blank line after the output for each set of input. Look at the output for sample input for details. Remember that it needs at least two consecutive numbers to form a consecutive sequence.

Sample Input                             Output for Sample Input

3

01711322396

01711322397

01711322398

7

01187239192

01711322396

01711322397

01711322398

01711322399

01711322400

01711389821

0

Problem setter: Shahriar Manzoor, Special Thanks: Syed Monowar Hossain

您可能對以下文章有興趣

[UVA][dp] 10201 - Adventures in Moving - Part IV

[UVA] 10469 - To Carry or not to Carry

[UVA][積分] 11346 - Probability

[UVA] 11474 - Dying Tree