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