单词 $v$ 的模板是指这样一个单词 $s$，使得 $s$ 在 $v$ 中的所有出现位置覆盖了整个单词 $v$（即单词 $v$ 的每个字母都出现在 $v$ 中某个与 $s$ 相等的连续片段内）。单词 $v$ 的准模板是指这样一个单词 $s$，使得 $s$ 是 $v$ 的一个子串（即连续字母片段），且 $s$ 是 $v$ 的某个超串的模板。下图展示了为什么单词 aabaa 是单词 aaaabaabaaaba 的准模板：
aabaa aabaa aabaa aabaa --------------------- aaaabaabaaaba
对于给定的单词 $v$，我们希望计算其准模板的数量以及其中最短的一个。
输入格式
标准输入的唯一一行包含一个非空单词 $v$，其长度不超过 $200\,000$ 个字母。它由小写英文字母组成。
输出格式
第一行应包含单词 $v$ 的准模板数量。第二行应包含作为 $v$ 的准模板的最短单词。如果存在多个这样的最短单词，则输出其中字典序最小的一个。
样例
输入 1
aaaabaabaaaba
输出 1
10 aabaa
说明
样例输入中的单词有 10 个准模板：aaaabaabaaab、aaaabaabaaaba、aaabaaba、aaabaabaa、aaabaabaaa、aaabaabaaaba、aabaa、aabaabaa、aabaabaaa 和 abaabaaa。