题目描述

给定一个仅包含小写字母的字符串 $S$，定义一个字符串 $T$ 是 $S$ 的“模板”，当且仅当：

• $T$ 是 $S$ 的子串；
• $T$ 能够“可超出头尾、可重叠”地覆盖 $S$。

例如：abac 是 acabacab 的“模板”，因为可以这样覆盖：

ac abac ab
abac abac abac

你需要计算对于给定的 $S$，有多少 $T$ 满足 $T$ 是 $S$ 的“模板”，并找出最短的“模板”，如果有多个，输出其中字典序最小的“模板”。

输入格式

输入包括一行，包含一个仅由小写字母构成的字符串 $S$。

输出格式

输出包括两行：

• 第一行：包含一个非负整数，表示 $S$ 的“模板”个数。
• 第二行：包含一个字符串 $T$，表示 $S$ 的最短“模板”，如果有多个，输出字典序最小的。

样例

样例输入

aaaabaabaaaba

样例输出

10
aabaa

数据范围

• 对于 30% 的数据：满足 $1\le |S|\le 500$。
• 对于 60% 的数据：满足 $1\le |S|\le 3000$。
• 对于 100% 的数据：满足 $1\le |S|\le 2\times 10^5$。