A template of a word $ v $ is such a word $ s $ that all occurrences of $ s $ within $ v $ cover the whole word $ v $ (i.e. each letter of the word $ v $ appears within some fragment of consecutive letters of $ v $ equal to $ s $). By quasi-template of a word $ v $ we mean such a word $ s $ that $ s $ is a substring (i.e. a fragment of consecutive letters) of $ v $ and $ s $ is a template of some superstring of $ v $. The figure below shows why the word aabaa is a quasi-template of the word aaaabaabaaaba:
aabaa aabaa aabaa aabaa --------------------- aaaabaabaaaba
For a given word $ v $ we would like to compute the number of its quasi-templates and the shortest one of them.
Input Format
The only line of the standard input contains a non-empty word $ v $ that is not longer than 200 000 letters. It consists of small letters of English alphabet.
Output Format
The first line of the standard output should contain the number of quasi-templates of word $ v $. The second line should contain the shortest word being a quasi-template of word $ v $. If there is more than one such shortest word, output the lexicographically smallest from the shortest quasi-templates.
Example
Input
aaaabaabaaaba
Output
10 aabaa
Notes
The word from the sample input has 10 quasi-templates: aaaabaabaaab, aaaabaabaaaba, aaabaaba, aaabaabaa, aaabaabaaa, aaabaabaaaba, aabaa, aabaabaa, aabaabaaa, and abaabaaa.