You are given a set of words. For each word you must create one of the following representations:

1. The whole word as it is, without changes.
2. A prefix of the word with a dot at its end.
3. 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.