BUZZW - Buzzwords

The word the is the most common three-letter word. It even shows up inside other words, such as "other" and "mathematics". Sometimes it hides, split between two words, such as "not here". Have you ever wondered what the most common words of lengths other than three are?

Your task is the following. You will be given a text. In this text, find the most common word of length one. If there are multiple such words, any one will do. Then count how many times this most common word appears in the text. If it appears more than once, output how many times it appears. Then repeat the process with words of length 2, 3, and so on, until you reach such a length that there is no longer any repeated word of that length in the text.

Input

The input consists of a sequence of lines. The last line of input is empty and should not be processed. Each line of input other than the last contains at least one but no more than one thousand uppercase letters and spaces. The spaces are irrelevant and should be ignored.

Output

For each line of input, output a sequence of lines, giving the number of repetitions of words of length 1, 2, 3, and so on. When you reach a length such that there are no repeated words of that length, output one blank line, do not output anything further for that input line, and move on to the next line of input.

Example

Input:
OTHER MATHEMATICS NOT HERE
AA


Output:
4
3
3
2
2

2

Note that the last line of the sample input is a blank line, and the last line of the sample output is a blank line.


Added by:Andres Tellez
Date:2011-08-23
Time limit:1s-1.610s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2017-07-12 09:01:15
I've done some asserts, it seems that the number of letters in the input string is at most between 500 and 1000 :). O(n * rep) passed, where rep is the length of the longest repeated word.
2011-09-28 16:08:52 biQar
@Andres Tellez - please specify the limit! And also i think the sample output is wrong! So, make it correct !

Last edit: 2011-09-28 16:09:59
2011-08-28 13:44:51 Walrus
Please specify the limits.
2011-08-24 09:38:56 Krunal Manik
Source of this problem is the Waterloo 2010 Fall 2 Contest.
Link : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=13&page=show_contest&contest=264
2011-08-24 09:09:51 [Rampage] Blue.Mary
O(n^2) TLE? Why don't you set the limit to 100000?

BTW, the sample output is wrong. The correct should be:
4
3
3
2
2

2



Last edit: 2011-08-24 09:26:19
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.