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.