The Secret Password

Sometimes programmers hide their passwords in very peculiar ways. In this problem, you are given a string \(S\) consisting of \(N\) lowercase letters (where \(5 \le N \le 5 \times 10^6\)). Binny "hides" his password in the following way:

He arranges the string \(S\) in a circle, and then for each letter in \(S\) he treats that letter as the starting point and reads the characters in clockwise order to form a new string. In other words, if \(S = s_1s_2\ldots s_N\), then for any starting position \(i\) (\(1 \le i \le N\)) the corresponding rotation is \[ R_i = s_i s_{i+1} \ldots s_N s_1 s_2 \ldots s_{i-1} \] After obtaining all \(N\) rotations, he sorts them in lexicographical order and selects the first string. Let \(P\) be the 1-indexed position in \(S\) from which this minimal rotation originates. Then the secret password is defined as \(P - 1\).

For example, if \(S = \texttt{alabala}\), the 7 rotations are:

a labala
labalaa
abalaal
balaala
alaalab
laalaba
aalabal

After sorting them lexicographically, the smallest rotation is aalabal, which originates from position 7 in the original string. Therefore, the secret password is \(7 - 1 = 6\).

inputFormat

The input consists of a single line containing the string \(S\), which is made up of lowercase letters and satisfies \(5 \le |S| \le 5 \times 10^6\).

outputFormat

Output a single integer: the secret password computed as the 1-indexed starting position of the lexicographically smallest cyclic rotation of \(S\) minus 1.

sample

alabala

6