Description

定义一个串s能匹配S当且仅当s能可超出头尾得覆盖S。 如下图。

给定S，问不同的s的个数。 S的长度 < = 200000。

Format

Input

The only line of the standard input contains a non-empty word that is not longer than 200000 letters. It consists of small letters of English alphabet.

Output

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.

Samples

aaaabaabaaaba

10
aabaa

Limitation

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