Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3079
Text

Time Limit: 1 Second      Memory Limit: 32768 KB

watashi's mm is so pretty as well as serious. All her English text is written under these following rules:

  1. There should be no more than 80 characters in a single line.
  2. Words are made up of letters({'A'..'Z' 'a'..'z'}), and consecutive words should be separated by only one blank({' '}). No word's length exceeds 80.
  3. Do not leave any spaces({' ', '\t', '\n'}) between the punctuations({',' '.' '?' '!'}) and the previous word. But do leave one blank between the punctuation and the following word. No punctuation should be used at the beginning of a line. There are no two consecutive punctuations
  4. '.', '?' and '!' can be only used at the end of a sentence. In addition, there is a '.', '?' or '!' at the end of any sentences.
  5. The first letter of a sentence must be a capital letter.
  6. All the text is made up of latters, punctuations and spaces.
  7. There is no extra space at the beginning and at the end of a line.

However, watashi is a very naughty boy. One day when his mm goes shopping and leaves her text at home, watashi begins his mischief. Firstly, the first letter of a sentence may be changed into lowercase. Then he adds some spaces between words or between word and punctuation. After that he deletes some spaces between word and punctuation. At last, he adds some spaces. When he divides a word by spaces, a hyphen ('-') will be appended to the first part. A word will never be divided more than once. Note that, after his mischief there may be more than 80 characters in a single line.

Imaginably, watashi's mm is so angry that she orders watashi to remake the text so that it will obey those original rules (all rules that are mentioned above). Unfortunately, watashi is known as a completely destroyer. It's almost impossible for him to do something constructive. To forbid parting from his mm, watashi turns to you for help. How poor watashi is! Given the text watashi makes, please write a program to output the original form of the text.

Input

The first line of input is the number of test cases T, then T test cases follow.

Each test case consists of only one paragraph, which is made up of characters (letters, punctuations or spaces). Each test case is ended by a line of "###".

Output

For each test case, output the original form of the text. Print a blank line between cases.

Sample Input

1
er   ? watashi mm is a beautiful girl    !  all her Eng-
lish   text     is  written under these following rules.there 
should   be no more than  eighty     characters in a sin-
gle line and please apply   the rules of automatically starting a new line.
###

Sample Output

Er? Watashi mm is a beautiful girl! All her English text is written under these
following rules. There should be no more than eighty characters in a single line
and please apply the rules of automatically starting a new line.

Author: MO, Luyi
Source: ZOJ Monthly, December 2008
Submit    Status