NSUBSTR  Substrings
You are given a string S which consists of 250000 lowercase latin letters at most. We define F(x) as the maximal number of times that some string with length x appears in S. For example for string 'ababa' F(3) will be 2 because there is a string 'aba' that occurs twice. Your task is to output F(i) for every i so that 1<=i<=S.
Input
String S consists of at most 250000 lowercase latin letters.
Output
Output S lines. On the ith line output F(i).
Example
Input:
ababa
Output:
3
2
2
1
1
hide comments
jagd:
20110822 15:06:20
Time limit: 1s2s ? 

Husnun Nashir:
20110822 15:06:20
please give me more test case 

ymGXX:
20110822 15:06:20
nice problem.I got AC after I found some mistakes. 

Siarhei Kulik:
20110822 15:06:20
The judge is OK now. Try to resubmit your solution. 

ymGXX:
20110822 15:06:20
Why I'm waiting for so long? 
Added by:  Sergey Kulik 
Date:  20110127 
Time limit:  0.100s1s 
Source limit:  44444B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Immagination 