Pseudo-template
A string (t) is considered a pattern of another string (s) if the combined occurrences of (t) within (s) completely cover (s). This means that every position in (s) is covered by at least one occurrence of (t). For example, the string (aba) is a pattern for (ababaaba).
A string (t) is defined as a pseudo-pattern of a string (s) if it meets the following criteria:
It is a substring of (s).
It is a pattern of some string that contains (s).
For example, the string (abaa) is a pseudo-pattern of (aabaabaab) because it appears as a substring and serves as a pattern for the string (abaabaabaabaa).
Given a string (s), your task is to determine the number of its pseudo-patterns and identify the shortest one.
Input
The input consists of a single string with a length ranging from (1) to (2 10^5), composed of lowercase Latin letters.
Output
On the first line, output the total number of pseudo-patterns for the given string. On the second line, output the shortest pseudo-pattern. If there are multiple pseudo-patterns of the shortest length, choose the lexicographically smallest one.