题目描述

从一个字符串 $p$ 开始。然后，按如下方式创建一个新字符串 $s$：从空字符串开始，插入 $p$。然后，在字符串中的某个位置（可能包括开头或结尾）再次插入 $p$。然后再一次，再一次。

例如，假设 $p$ 是 "hello"。从空字符串开始，可以按如下方式生成一个字符串 $s$（每次新插入的 $p$ 用 粗体 表示）：

2. hello
3. hhelloello
4. hhelloelhellolo
5. hhehellolloelhellolo

因此，经过 5 步后，字符串 $s$ 为 hhehellolloelhellolo。

给定最终的字符串 $s$，找出可能生成 $s$ 的最短字符串 $p$。如果存在多个长度相同的最短字符串，则找出字典序最小的那个。

输入格式

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。每个输入由一行组成，包含一个字符串 $s$。该字符串仅包含小写字母，长度至少为 $1$，至多为 $200$。

输出格式

输出一行，包含字符串 $p$，即可能生成 $s$ 的最短字符串。

hhehellolloelhellolo

hello

提示

翻译由 DeepSeek V3.2 完成