ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Qualification round of Eastern subregional contest 2015

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Reductions

Time limit: 0.5 second
Memory limit: 32 MB
Language limit: C, C++, Pascal
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.

Input

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.

Output

Print list of reductions for all words in the same order in which words appeared in the input.

Samples

inputoutput
4
aba
abaca
add
dd
aba
a-ca
add
dd
2
aa
aaaaa
aa
aaa.
2
abc
abcdabc
abc
abcd.
Problem Author: Mikhail Rubinchik (prepared by Egor Shchelkonogov)
To submit the solution for this problem go to the Problem set: 2077. Reductions