문자열 늘이기

문자열 $p$로 새 문자열 $s$를 다음처럼 만든다. 빈 문자열에서 시작해 $p$를 넣는다. 그다음 지금 문자열에서 맨 앞과 맨 뒤를 포함한 아무 위치나 골라 그 자리에 $p$를 한 번 더 넣는다. 이 과정은 원하는 만큼 되풀이할 수 있다.

$p$가 hello인 경우를 보자. 빈 문자열에서 시작하면 문자열이 다음처럼 자랄 수 있다. 각 단계에서 새로 넣은 $p$는 굵게 표시했다.

1. (빈 문자열)
2. hello
3. hhelloello
4. hhelloelhellolo
5. hhehellolloelhellolo

hello를 네 번 넣었고, 마지막 문자열은 hhehellolloelhellolo이다.

완성된 문자열 $s$가 주어진다. $s$를 만들어 낼 수 있는 가장 짧은 문자열 $p$를 구하라. 길이가 같은 $p$가 여러 개면 사전순으로 가장 앞서는 것을 구하라.

첫째 줄에 문자열 $s$가 주어진다. $s$는 알파벳 소문자로만 이루어지고, 길이는 1 이상 200 이하이다.

첫째 줄에 $s$를 만들어 낼 수 있는 가장 짧은 문자열 $p$를 출력한다. 그런 $p$가 여러 개면 사전순으로 가장 앞서는 것을 출력한다.