Description

Define that a string $s$ can match $S$ if and only if $s$ can cover $S$ while being allowed to extend beyond both the beginning and the end of $S$, and $|s| \le |S|$, and $s$ must be a substring of $S$.

As shown in the figure below.

Given $S$, find the number of distinct strings $s$ and the shortest such $s$. If there are multiple answers, output the lexicographically smallest one.

Input Format

One line containing a string $S$.

Output Format

The first line contains an integer indicating the number of solutions.

The second line contains a string, the shortest $s$. If there are multiple answers, output the lexicographically smallest one.

aaaabaabaaaba

10
aabaa

Hint

Valid strings are: aaaabaabaaab, aaaabaabaaaba, aaabaaba, aaabaabaa, aaabaabaaa, aaabaabaaaba, aabaa, aabaabaa, aabaabaaa, abaabaaa.

Constraints: $|S| \le 2\times 10^5$.

Translated by ChatGPT 5