Рассмотрим строку S = s1s2s3 sn−1sn над алфавитом Σ. Циклическим расширением порядка m строки S назовем строку s1s2s3 sn−1sns1s2 из m символов; это значит, что мы приписываем строку S саму к себе, пока не получим требуемую длину, и берем префикс длины m.

Рассмотрим строку S = s1s2s3 sn−1sn над алфавитом Σ. Циклическим расширением
порядка m строки S назовем строку s1s2s3 sn−1sns1s2 из m символов; это значит, что
мы приписываем строку S саму к себе, пока не получим требуемую длину, и берем префикс
длины m.
Циклической строкой ˜ S назовем бесконечное циклическое расширение строки S.
Рассмотрим суффиксы циклической строки ˜ S. Очевидно, существует не более |S| различ
ных суффиксов: (n + 1)-ый суффикс совпадает с первым, (n + 2)-ой совпадает со вторым,
и так далее. Более того, различных суффиксов может быть даже меньше. Например, если
S =abab, первые четыре суффикса циклической строки ˜ S — это:
˜
S1 = ababababab
˜
S2 = bababababa
˜
S3 = ababababab
˜
S4 = bababababa
Здесь существует всего два различных суффикса, в то время как |S| = 4.
Отсортируем первые |S| суффиксов ˜ S лексикографически. Если два суффикса совпадают,
первым поставим суффикс с меньшим индексом. Теперь нас интересует следующий вопрос:
на каком месте в этом списке стоит сама строка ˜ S?
Например, рассмотрим строку S = cabcab:
(1)
(2)
(3)
(4)
(5)
(6)
˜
S2 = abcabcabca
˜
S5 = abcabcabca
˜
S3 = bcabcabcab
˜
S6 = bcabcabcab
˜
S1 = cabcabcabc
˜
S4 = cabcabcabc
Здесь циклическая строка ˜ S = ˜ S1 находится на пятом месте.
Вам дана строка S. Ваша задача — найти позицию циклической строки ˜ S в описанном
порядке.
Формат входных данных
Во входном файле записана единственная строка S (1 ⩽ |S| ⩽ 1000000), состоящая из
прописных латинских букв.
Формат выходных данных
В выходной файл выведите единственное число — номер строки ˜ S в описанном порядке
среди первых |S| суффиксов.
Примеры
stdin
abracadabra
stdout
3
cabcab
5
Z-функция.Нужно решить на с++