Calloc

Gaia is referred to in literature as a living planet, a collective conscience arising from putting together each individual conscience of its inhabitants.

Collective memory is one of the most precious resources on Gaia. Each time an event takes place, it gets backed up in several places in order to minimize information loss. From time to time, as it happens, some new pieces of information need to be memorized, and the gaians want to make the memorizing process as efficient as possible. Thus, they designed a new method for keeping track of consecutive chunks of information.

The method goes as follows: having some strings of characters which represent the pieces of data to keep in mind, they form a single string which contains each of the input strings as substrings (i.e. it contains all the letters of each input string in the same order, not necessarily on consecutive positions).

Scoring

The gaians want to find the best possible method for storing their data. Therefore, given a participant's solution on a given test, they will first check if it matches the constraints, and then compare it to the best length found by all participants (and the official solution, respectively). The solution's score will be computed as the ratio between the best solution length and the participant's solution length.

Input

Each line of the input will be a string of letters from the English alphabet, either lowercase or uppercase, representing the information which is meant to be memorized.

Output

A single line, containing a string which has all of the strings in the input as substrings.

Constraints

• The sum of lengths of all input strings does not exceed 10⁶.
• There is one pretest, identical to the sample testcase. You won't know the score of your solution during the contest, only whether or not the output is valid.
• Multiple submissions and submission time still apply a penalty to your score.

Sample