% Origin: 20100422, SPbSU, Spring 2010, Group A, Fourth Training - Strings
% Author: Ivan Kazmenko
% Text Author: Ivan Kazmenko
% Tests Author: Ivan Kazmenko

\begin{problem}{Генератор строки}
{\textsl{стандартный ввод}}{\textsl{стандартный вывод}}
%{genstr.in}{genstr.out}
{2 секунды}{256 мебибайт}{}

\textit{Генератором} строки назовём наименьший префикс, который нужно
повторить (возможно, нецелое число раз), чтобы получить эту строку.
Например, генератор строки <<\t{ababab}>> "--- это строка <<\t{ab}>>,
генератор строки <<\t{abcabca}>> "--- это строка <<\t{abc}>>, генератором
строки <<\t{abcd}>> является она сама.

По данной строке найдите её генератор.

\InputFile

В первой строчке входного файла задана непустая строка, состоящая
из строчных букв латинского алфавита. Длина строки не превышает
одного миллиона символов.

\OutputFile

В первой строчке выходного файла выведите генератор данной строки.

\Examples

\begin{example}
\exmp{
ababab
}{
ab
}%
\exmp{
abcabca
}{
abc
}%
\exmp{
abcd
}{
abcd
}%
\end{example}

\end{problem}
