从一个字符串 $p$ 开始。现在，创建一个新字符串 $s$，方法如下：从空字符串开始，插入 $p$。然后，选择字符串中的某个位置（包括最开头或最末尾），再次插入 $p$。如此反复。
例如，假设 $p$ 为 “hello”。从空字符串开始，字符串 $s$ 的生成过程可能如下（每次新插入的 $p$ 以粗体显示）：
- hello
- hhelloello
- hhelloelhellolo
- hhehellolloelhellolo
因此，经过 5 步后，字符串 $s$ 为 hhehellolloelhellolo。
给定最终字符串 $s$，找出能够生成 $s$ 的最短字符串 $p$。如果存在多个长度相同的最短字符串，则选择字典序最小的那一个。
输入格式
每个输入包含一个测试用例。请注意，你的程序可能会在不同的输入上运行多次。每个输入由单行字符串 $s$ 组成。字符串仅包含小写字母，长度至少为 1，至多为 200。
输出格式
输出一行字符串 $p$，即能够生成 $s$ 的最短字符串。
样例
输入格式 1
hhehellolloelhellolo
输出格式 1
hello