Start with a string . Now, create a new string , like this: Start with the empty string, and insert . Then, choose some position in the string (including, possibly, the very beginning or the very end), and insert again. And again. And again.
For example, suppose is "hello". Starting with the empty string, a string might be generated like this (each new insertion of is in bold):
hello
hhelloello
hhelloelhellolo
hhehellolloelhellolo
So, after 5 steps, the string is hhehellolloelhellolo.
Given the final string , find the shortest string which could have generated . If there’s more than one with the shortest length, find the one that comes first alphabetically.
输入格式
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each input consists of a single line with a single string . The string will consist of only lower case letters, and will be at least , and at most , characters long.
输出格式
Output a single line with the string , which is the shortest possible string that could generate .
