#3499. PA2009 Quasi-template

内存限制:256 MiB 时间限制:10 Sec

题目描述

定义一个串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.