Cyclic Shifts

A cyclic shift of the string s is the string s_k+1s_k+2…s_ns₁s₂…s_k for some k (0 ≤ k < n) where n is the length of the string s.

For a given string, construct all cyclic shifts, sort them lexicographically, output the last column, and find the position of the original string in this list.

Input

The only line of input contains a string consisting of characters with ASCII codes 33 to 127. The string length can be up to 10⁵.

Output

In the first line of the output, print the position of the given string in the sorted list of cyclic shifts. If there are several such positions, then the position with the smallest number should be printed. In the second line, output the last column of the sorted cyclic shift table.

Sample

Note

Firstly, we write out all 6 cyclic shifts of the string "abraka" and sort the resulting list lexicographically:

Original list	Sorted list
abraka brakaa rakaab akaabr kaabra aabrak	aabrak abraka akaabr brakaa kaabra rakaab

Now we see that the original word is in the 2-nd position in the sorted list, and the last column is the string "karaab".

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!