You are given a string S=s1s2..s|S|S=s1s2..s|S| containing only lowercase English letters. For each integer i∈[1,|S|]i∈[1,|S|] , please output how many substrings slsl+1...srslsl+1...sr satisfy the following conditions:
∙∙r−l+1r−l+1 equals to ii.
∙∙ The substring slsl+1...srslsl+1...sr is a palindrome string.
∙∙slsl+1...s⌊(l+r)/2⌋slsl+1...s⌊(l+r)/2⌋ is a palindrome string too.
|S||S| denotes the length of string SS.
A palindrome string is a sequence of characters which reads the same backward as forward, such as madammadam or racecarracecar or abbaabba.
Input
There are multiple test cases.
Each case starts with a line containing a string S(1≤|S|≤3×105)S(1≤|S|≤3×105) containing only lowercase English letters.
It is guaranteed that the sum of |S||S| in all test cases is no larger than 4×1064×106.
Output
For each test case, output one line containing |S||S| integers. Any two adjacent integers are separated by a space.