Дано рядок s. Знайти такий мінімальний за довжиною рядок t, що s можна подати у вигляді конкатенації однієї або декількох рядків t.
Єдиний рядок s (1 ≤ |s| ≤ 5·10^6), шо містить лише літери латинського алфавіту.
Довжина шуканого рядка t.