You are given a set of words. For each word you must create one of the following representations:
- The whole word as it is, without changes.
- A prefix of the word with a dot at its end.
- A prefix and a suffix of the word separated by a hyphen.
Let us call this new representation of a word reduction.
Word fits a given reduction if it is possible to reconstruct the word from the reduction
by replacing dot/hyphen with a (possibly empty) string.
Your task is to create a reduction for each word in a given set, so that
only one word would fit each reduction.
For example, if you are given two words “information” and “instruction” you
can’t create a reduction “in-ion” for either of them, because both can be reconstructed
from it. You can, however, create reductions “inf.” and “ins.”.
If you are given two words “bar” and “barn” you can’t use reduction “bar.”, but
can create reductions “bar” and “b-n”.
From all possible sets of reductions you must choose one with minimal aggregated
length of reductions. If there are several of those, choose one, where maximal amount
of words are left in their initial form. If there are still several solutions, choose one with
minimal amount of reductions with a hyphen. Lastly, if there is still an ambiguity, choose
a solution with maximal aggregated length of prefixes before hyphens.
It is guaranteed, that there is a single solution, that meets all of the conditions above.
First line contains a number of words n (1 ≤ n ≤ 1 000 000).
Next n lines contain one word each. All words are different and consist of
lower-case latin letters. Their aggregated length is not greater than 1 000 000.
Words in the input are ordered lexicographically.
Print list of reductions for all words in the same order in which words appeared in the input.
Problem Author: Mikhail Rubinchik (prepared by Egor Shchelkonogov)