题目描述

定义一个串s能匹配S当且仅当s能可超出头尾得覆盖S。  如下图。
  
给定S，问不同的s的个数。
S的长度 <  = 200000。

输入格式

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.

输出格式

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.