Problem: Palindromic characteristics of string s with length |s| is a sequence of |s| integers, where k-th number is the total number of non-empty substrings of s which are k-palindromes.

A string is 1-palindrome if and only if it reads the same backward as forward.

A string is k-palindrome (k > 1) if and only if: 

  1. Its left half equals to its right half. 
  2. Its left and right halfs are non-empty (k - 1)-palindromes. 



The left half of string t is its prefix of length ⌊|t| / 2⌋, and right half — the suffix of the same length. ⌊|t| / 2⌋ denotes the length of string t divided by 2, rounded down.

Note that each substring is counted as many times as it appears in the string. For example, in the string "aaa" the substring "a" appears 3 times.

Input

The first line contains the string s (1 ≤ |s| ≤ 5000) consisting of lowercase English letters.

Output

Print |s| integers — palindromic characteristics of string s.

Examples

Input

abba


Output

6 1 0 0 


Input

abacaba


Output

12 4 1 0 0 0 0 

Note

In the first example 1-palindromes are substring «a», «b», «b», «a», «bb», «abba», the substring «bb» is 2-palindrome. There are no 3- and 4-palindromes here.

Solution (in PYTHON):

Solution:
from sys import stdin

class pal_node:
    def __init__(self):
		# start and end indices of the palindrome
		self.start = None
		self.end = None
	
		# length of the palindrome
		self.length = None
	
		# edges to the palindromes that are formed by padding the same 
		# letter on the front and back of this palindrome
		self.pad = [None for _ in xrange(26)]
						
		# edge to this palindrome's longest palindromic suffix                        
		self.suffix = None
		
		# number of occurrences of this palindrome
		self.num_occ = 1
		
		self.characteristic = 1
    

class pal_tree: 
	def __init__(self, s):
		self.s = s
		self.root1 = pal_node()
		self.root2 = pal_node()
		self.root1.length = -1
		self.root2.length = 0
		self.root1.suffix = self.root1
		self.root2.suffix = self.root1
		self.curr_node = self.root1
		self.palindromes = [] # stores the nodes in the order they're created
		self.num_dist_pal = 0	
	 
	def insert(self, i):	
		temp = self.curr_node
		
		# look for X such that s[i]Xs[i] is a palindrome
		while True:
			curr_length = temp.length
			if i - curr_length >= 1 and self.s[i] == self.s[i-curr_length-1]:
				break
			temp = temp.suffix		
	
		# check if s[i]Xs[i] already exists
		if temp.pad[ord(self.s[i])-ord('a')]:
			self.curr_node = temp.pad[ord(self.s[i])-ord('a')]
			self.curr_node.num_occ += 1
			return
	
		new_node = pal_node()
		temp.pad[ord(self.s[i])-ord('a')] = new_node
		new_node.length = temp.length + 2
		new_node.start = i - new_node.length + 1
		new_node.end = i
		new_pal = self.s[new_node.start:new_node.end+1]
		self.num_dist_pal += 1
		self.palindromes.append(new_node)
	
		if new_node.length == 1:
			new_node.suffix = self.root2
			self.curr_node = new_node
			return
	
		temp = temp.suffix
		while True:
			curr_length = temp.length
			if i - curr_length >= 1 and self.s[i] == self.s[i-curr_length-1]:
				break
			temp = temp.suffix
	
		new_node.suffix = temp.pad[ord(self.s[i])-ord('a')]
		
		# get the characteristic of the new node
		temp = new_node
		while temp.length > new_node.length/2:
			temp = temp.suffix
		if temp.length == new_node.length/2:
			new_node.characteristic = temp.characteristic + 1
			
		self.curr_node = new_node	
		
	def compute_occurrences(self):
		for i in xrange(-1, -self.num_dist_pal-1, -1):
			self.palindromes[i].suffix.num_occ += self.palindromes[i].num_occ
				
s = stdin.readline().strip()
 
tree = pal_tree(s)
      
for i in xrange(len(s)):
    tree.insert(i)  
    
tree.compute_occurrences()

ch = [0]*len(s)
for pal in tree.palindromes:
	for c in xrange(1, pal.characteristic+1):
		ch[c-1] += pal.num_occ
print ' '.join(map(str, ch))