String Stretching

Time limit1sMemory limit256 MB

Summary

Given a lowercase string up to length 200, find the shortest base string that builds it by repeated insertions anywhere, breaking ties alphabetically.

Level: Medium7 of 10
Topics: Dynamic programming, String, Brute force
Solved: No attempts yet

Problem

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.

(the empty string)
hello
hhelloello
hhelloelhellolo
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.

Input

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

Output

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.

Examples3

Example 1
Input
```
hhehellolloelhellolo
```
Expected output
```
hello
```
Example 2
Input
```
a
```
Expected output
```
a
```
Example 3
Input
```
aabaabaa
```
Expected output
```
aaba
```