A word is a string of two or more letters while a code is a string of one or more distinct words in lexicographic order. Thus a string of letters may represent either a word or a code. An optimum code is a code that contains the maximum number of words.

For a given string of letters there may be one or more optimum codes. The optimum code of top priority is the optimum code that appears at the top when all optimum codes are arranged in lexicographic order.

Given a string of letters, you are required to write a program that finds the following:

• The total number of words, m in an optimum code,
• The total number of optimum codes, n represented by the string,
• The optimum code of top priority, the top-code.

Input

Input consists of multiple test cases.

For each test case there is only one line of input. It contains a string of at most 100 letters.

A line consisting of a single letter terminates input.

Output

For each test case, present output in two lines.

The first line gives the two integers m and n defined above. The next line gives the optimum code of top priority, the top-code.

Example

Input:
aaaaaa
words
lexicographic
a

Output:
2 1
aa aaaa
1 1
words
3 2
lexic og raphic