Two strings $x$ and $y$ are distinguishable with respect to $S$ if and only if there exists a string $z$ such that $xz$ is a suffix of $S$ and $yz$ is not a suffix of $S$, or $yz$ is a suffix of $S$ and $xz$ is not a suffix of $S$.
For example, "ab" and "b" are distinguishable with respect to "abbab" by choosing $z = \text{"ab"}$.
Two suffixes $x$ and $y$ are incomparable if and only if for all non-empty prefixes $x_1$ of $x$ and non-empty prefixes $y_1$ of $y$, $x_1$ and $y_1$ are distinguishable. For example, "ab" and "bab" are incomparable.
Given a string $s$, find a suffix set of $s$ that is as large as possible. Under the condition that the set size is maximized, maximize the sum of the lengths of the strings in the set.
Input
Multiple test cases.
Each line contains a string $s$.
Output
For each test case, output two integers representing the size of the suffix set and the sum of the lengths of the strings in the set.
Examples
Input 1
abbab aaaaa abacaba
Output 1
2 6 1 5 3 7
Note
The results correspond to the sets: (ab, bbab), (aaaaa), and (a, ba, caba) respectively.
Constraints
- 10%, each string length does not exceed 10.
- 20%, each string length does not exceed 20.
- An additional 30%, the sum of lengths of all strings does not exceed 5000.
- 100%, the number of test cases does not exceed 1024, and the sum of lengths of strings $s$ does not exceed $10^5$.