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:</p>

             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.

입력 형식

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.

출력 형식

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.

예제 입력

aaaabaabaaaba

예제 출력

10
aabaa

힌트

The word from the sample input has 10 quasi-templates: aaaabaabaaab, aaaabaabaaaba, aaabaaba, aaabaabaa, aaabaabaaa, aaabaabaaaba, aabaa, aabaabaa, aabaabaaa, and abaabaaa.