H. Brevity is Soul of Wit

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

As we communicate, we learn much new information. However, the process of communication takes too much time. It becomes clear if we look at the words we use in our everyday speech.

We can list many simple words consisting of many letters: "information", "technologies", "university", "construction", "conservatoire", "refrigerator", "stopwatch", "windowsill", "electricity", "government" and so on. Of course, we can continue listing those words ad infinitum.

Fortunately, the solution for that problem has been found. To make our speech clear and brief, we should replace the initial words with those that resemble them but are much shorter. This idea hasn't been brought into life yet, that's why you are chosen to improve the situation.

Let's consider the following formal model of transforming words: we shall assume that one can use $n$ words in a chat. For each words we shall introduce a notion of its shorter variant. We shall define shorter variant$ of an arbitrary word $s$ as such word $t$, that meets the following conditions:

  • it occurs in $s$ as a subsequence$,
  • its length ranges from one to four characters.

In other words, the word $t$ consists at least of one and at most of four characters that occur in the same order in the word $s$. Note that those characters do not necessarily follow in $s$ immediately one after another. You are allowed not to shorten the initial word if its length does not exceed four characters.

You are given a list of $n$ different words. Your task is to find a set of their shortened variants. The shortened variants of all words from the list should be different.

Оролт

The first line of the input file contains the only integer $n$ $(1 ≤ n ≤ 200)$. Then $n$ lines contain a set of different non-empty words that consist of lowercase Latin letters. The length of each word does not exceed $10$ characters.

Гаралт

If the solution exists, print in the output file exactly $n$ lines, where the $i$-th line represents the shortened variant of the $i$-th word from the initial set. If there are several variants to solve the problem, print any of them. If there is no solution, print -1$.

Орчуулсан: [орчуулагдаж байгаа]

Жишээ тэстүүд

Оролт
6
privet
spasibo
codeforces
java
marmelad
normalno
Гаралт
pret
sps
cdfs
java
mama
norm
Оролт
5
aaa
aa
a
aaaa
aaaaa
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...