Задачі
Циклічні суфікси (Easy)
Циклічні суфікси (Easy)
Розглянемо рядок \textbf{S = s_1s_2s_3...s_\{n - 1\}s_n} над алфавітом \textbf{Σ}. \textit{Циклічним розширенням} порядку \textbf{m} рядка \textbf{S} назвемо рядок\textbf{s_1s_2s_3...s_\{n - 1\}s_ns_1s_2...} з \textbf{m} символів; це значить, що ми дописуємо рядок \textbf{S} сам до себе, доки не отримаємо потрібну довжину, і беремо префікс довжини \textbf{m}.
\textit{Циклічним рядком} \textbf{Š} назвмо нескінченне циклічне розсширення рядка \textbf{S}.
Розглянемо суфікси циклічного рядка \textbf{Š}. Очевидно, існує не більше |\textbf{S}| різних суфіксів: (\textbf{n+1})-ий суфікс співпадає з першим, (\textbf{n+2})-ий співпадає з другим, і так далі. Більше того, різних суфіксів може бути навіть менше. Наприклад, якщо \textbf{S = abab}, перші чотири суфікси циклічного рядка \textbf{Š} - цео:
\textbf{Š}_1 = \textbf{ababababab}...\textbf{Š}_2 = \textbf{bababababa}...\textbf{Š}_3 = \textbf{ababababab}...\textbf{Š}_4 = \textbf{bababababa}...
Тут існує усього два різних суфікси, у той час як |\textbf{S}| = \textbf{4}.
Відсортуємо перші |\textbf{S}| суфіксів \textbf{Š} лексикографічно. Якщо два суфікси співпадають, першим поставимо суфікс з меншим індексом. Тепер нас цікавить наступне питання: на якому місці у цьомц списку стоїть сам рядок \textbf{Š}?
Наприклад, розглянемо рядок \textbf{S = cabcab}:
(1) \textbf{Š}_2 = \textbf{abcabcabca}...(2) \textbf{Š}_5 = \textbf{abcabcabca}...(3) \textbf{Š}_3 = \textbf{bcabcabcab}...(4) \textbf{Š}_6 = \textbf{bcabcabcab}...(5) \textbf{Š}_1 = \textbf{cabcabcabc}...(6) \textbf{Š}_4 = \textbf{cabcabcabc}...
Тут циклічний рядок \textbf{Š} = \textbf{Š}_1 знаходиться на п'ятому місці.
Вам задано рядок \textbf{S}. Ваша задача - знайти позицію циклічного рядка \textbf{Š} у описаному порядку.
\InputFile
У вхідному файлі записано єдиний рядок \textbf{S} (\textbf{1} ≤ |\textbf{S}| ≤ \textbf{30}), який складається з прописних латинських літер.
\OutputFile
У вихідний файл виведіть єдине число - номер рядка \textbf{Š} у описаному порядку серед перших |\textbf{S}| суфіксів.
Вхідні дані #1
abracadabra
Вихідні дані #1
3