Dictionary

The authors of a new all-in-one encyclopedia arranged the titles in the order they consider most suitable for their readers. This order is not always alphabetical, because they want to reveal certain peculiar relationships between the titles. Even so, they still want readers to be able to look titles up quickly.

To make this possible, they place a carefully computed number of spaces before every title in the list. They call the resulting structure a dictionary.

A dictionary is a list of words with some number of spaces before certain words. Its format is described by constraints on runs of consecutive words that start with the same letter. Every maximal run of consecutive words starting with the same letter must satisfy the following rules:

• The first word of the run has no leading spaces. Every word after it has at least one leading space.

• If you

  • delete the first word of the run,
  • delete one space before every remaining word, and
  • delete the first letter of every remaining word,

  then the resulting sequence is again a dictionary.

The examples below clarify this definition.

Your task is to write a program that turns a given list of words into a dictionary by adding a suitable number of spaces before certain words, while preserving the original order of the words.

The input consists of at least one and at most 100000 words. Each word consists of at least one and at most 10 lower-case letters. There are no leading or trailing spaces. There are no blank lines between the words, but there may be an arbitrary number of blank lines at the end of the input.

Print the original words in the same order, without any trailing spaces but with the appropriate number of leading spaces, so that the resulting list of words is a dictionary. There must be no blank lines between the words, but there may be an arbitrary number of blank lines at the end of the output.