Розглянемо рядок \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{1000000}), який складається з прописних латинських літер. \OutputFile У вихідний файл виведіть єдине число - номер рядка \textbf{Š} у описаному порядку серед перших |\textbf{S}| суфіксів.