시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 14 1 1 100.000%

문제

Start with a string p. Now, create a new string s, like this: Start with the empty string, and insert p. Then, choose some position in the string (including, possibly, the very beginning or the very end), and insert p again. And again. And again.

For example, suppose p is “hello”. Starting with the empty string, a string s might be generated like this (each new insertion of p is in bold):

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

So, after 5 steps, the string s is hhehellolloelhellolo. Given the final string s, find the shortest string p which could have generated s. 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 s. The string will consist of only lower case letters, and will be at least 1, and at most 200, characters long.

출력

Output a single line with the string p, which is the shortest possible string that could generate s.

예제 입력

hhehellolloelhellolo

예제 출력

hello

힌트