For a string of length and a positive integer (), a non-empty substring of is called a -substring if the substring appears exactly times. Such occurrences are not necessarily disjoint, i.e., are possibly overlapping. For example, if , the -substrings of for every are as follows:
There are four 1-substrings in , , , , and because these substrings appear exactly once in . Note that is not a 1-substring because it appears twice.
There are four 2-substrings in , , , , and . The substring appears exactly twice without overlapping. Two occurrences of the substring are overlapped at a common character , but it does not appear three times or more.
There is only one 3-substring in , .
Neither 4-substrings nor 5-substrings exist in .
For a -substring of , let be the maximum number of the disjoint occurrences of in . For example, a 2-substring can be selected twice without overlapping, that is, the maximum number of the disjoint occurrences is two, so . For a 2-substring , it cannot be selected twice without overlapping, so . For a 3-substring , it can be selected three times without overlapping, which is the maximum, so .
Let be the length of the longest one among all -substring with the largest for . For example, for and is as follows:
For , all 1-substrings can be selected only once without overlapping, so . Thus, the longest one among all 1-substrings with is , so .
For , for , but for the other 2-substrings , , . Among 2-substrings with , and are the longest ones, so .
For , because there is only one 3-substring .
For , there are no -substrings, so and .
Given a string of length , write a program to output values of from to . For the above example, the output should be .
输入格式
Your program is to read from standard input. The input starts with a line containing the string consisting of () lowercase alphabets.
输出格式
Your program is to write to standard output. Print exactly one line. The line should contain exactly non-negative integers, separated by a space, that represent from to in order, that is, . Note that should be zero if there is no -substring for some .
