String Stretching

Build a new string $s$ from a string $p$ like this. Begin with the empty string and insert $p$. Then pick any position in the current string, including the very beginning and the very end, and insert $p$ there again. Repeat this as many times as you like.

Suppose $p$ is hello. Starting from the empty string, the string can grow like this, with the copy inserted at each step in bold.

1. (the empty string)
2. hello
3. hhelloello
4. hhelloelhellolo
5. hhehellolloelhellolo

Four copies of hello went in, so the final string is hhehellolloelhellolo.

You are given the final string $s$. Find the shortest string $p$ that could have produced it. If several strings of that length could have produced $s$, find the one that comes first in alphabetical order.

The first line contains the string $s$. It consists of lowercase letters only, and its length is between 1 and 200.

Print on the first line the shortest string $p$ that could have produced $s$. If more than one string of that length works, print the one that comes first in alphabetical order.