Matching Substring Pattern

Given a string (S), a substring (s) is said to match (S) if and only if copies of (s) can cover (S) by extending beyond its head and tail. In other words, if we form an infinite periodic string by repeating (s), then (S) must appear as a contiguous segment in it. Moreover, the length of (s) must not exceed the length of (S), and (s) must be a substring of (S).

More formally, let (S) be of length (N) and let (s) be of length (L) where (1 \le L \le N). We say that (s) matches (S) if there exists an offset (r) with (0 \le r < L) such that for every index (i) (using 0-indexing) in (S), the characters assigned to positions in (s) via the mapping (s[(i+r) \bmod L]) are consistent. That is, for every residue class (k) with (0 \le k < L), all characters (S[i]) with (i \equiv k - r \pmod{L}) are the same. Finally, the string (s) constructed in this way must occur as a substring of (S).

Your task is to calculate two things:

• The number of distinct substrings \(s\) of \(S\) that match \(S\) under the conditions above.
• The shortest matching substring \(s\). If there are several with the same shortest length, output the lexicographically smallest one.
It is guaranteed that at least one matching substring exists.

inputFormat

A single line containing the string (S). (S) consists of lowercase English letters.

outputFormat

Output two items separated by a space: first, the number of distinct matching substrings (s), and second, the shortest matching substring (s) (if there are multiple, output the lexicographically smallest one).

sample

aba

2 ab