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:   Its left half equals to its right half.  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.

Difficulty: interview

Starter code:

Solutions:
s = input()
n = len(s)

dp = [[0 for i in range(n - le + 1)] for le in range(n + 1)]
ans = [0 for i in range(n + 1)]

for le in range(1, n + 1):
    for l in range(0, n - le + 1):
        r = l + le
        if s[l] != s[r - 1]:
            continue
        if le == 1:
            dp[1][l] = 1
            ans[1] += 1
        elif le == 2:
            ans[2] += 1
            dp[2][l] = 2
        elif dp[le - 2][l + 1]:
            v = 1
            m = (l + r) // 2
            st = m + 1 if le & 1 else m
            le2 = m - l
            q = dp[le2][l]
            if q:
                v = q + 1

            ans[v] += 1
            dp[le][l] = v


for i in range(n - 1, 0, -1):
    ans[i] += ans[i + 1]

print(*ans[1:])


s = input()
n = len(s)

dp = [[0 for i in range(n - le + 1)] for le in range(n + 1)]
ans = [0 for i in range(n + 1)]

for le in range(1, n + 1):
    for l in range(0, n - le + 1):
        r = l + le
        if s[l] != s[r - 1]:
            continue
        if le == 1:
            dp[1][l] = 1
            ans[1] += 1
        elif le == 2:
            ans[2] += 1
            dp[2][l] = 2
        elif dp[le - 2][l + 1]:
            v = 1
            m = (l + r) // 2
            st = m + 1 if le & 1 else m
            le2 = m - l
            q = dp[le2][l]
            if q:
                v = q + 1

            ans[v] += 1
            dp[le][l] = v


for i in range(n - 1, 0, -1):
    ans[i] += ans[i + 1]

print(*ans[1:])

s = input()
n = len(s)

dp = [[0 for i in range(n - le + 1)] for le in range(n + 1)]
ans = [0 for i in range(n + 1)]

for le in range(1, n + 1):
    for l in range(0, n - le + 1):
        r = l + le
        if s[l] != s[r - 1]:
            continue
        if le == 1:
            dp[1][l] = 1
            ans[1] += 1
        elif le == 2:
            ans[2] += 1
            dp[2][l] = 2
        elif dp[le - 2][l + 1]:
            v = 1
            m = (l + r) // 2
            st = m + 1 if le & 1 else m
            le2 = m - l
            q = dp[le2][l]
            if q:
                v = q + 1

            ans[v] += 1
            dp[le][l] = v


for i in range(n - 1, 0, -1):
    ans[i] += ans[i + 1]

print(*ans[1:])

s = input().strip()
n = len(s)
pl = [0]*(n+1)

dp = [[0]*n for i in range(n)]

for i in range(n):
	for j in range(n-i):
		l = j+i
		if i == 0:
			dp[j][l] = 1
			pl[1] +=1
		elif  i == 1:
			if s[j] == s[l]:
				dp[j][l] = 2
				pl[2] += 1
		else:
			if s[j] == s[l] and dp[j+1][l-1] > 0:
				if (i+1)%2 == 0:
					mid = int((i+1)/2)-1
					dp[j][l] = dp[j][j+mid]  + 1
					pl[dp[j][l]] += 1
				else:
					mid = int((i+1)/2)-1
					dp[j][l] = dp[j][j+mid]  +1	
					pl[dp[j][l]] += 1

ans = ''
for i in range(n-1,-1,-1):
	pl[i] += pl[i+1]
for i in  range(1,n+1):
	ans = ans + str(pl[i]) + ' '
print(ans)

s = input()

size = len(s)

dp = [[0 for l in range(size)] for li in range(size)]

ans = [0]*(size+1)

for i in range(1, size+1):
    if i == 1:
        for j in range(0, size):
            dp[j][j] = 1
            ans[1] += 1
    elif i == 2:
        for j in range(0, size-1):
            if s[j+1] == s[j]:
                dp[j][j+1] = 2
                ans[1] += 1
                ans[2] += 1
            else:
                dp[j][j+1] = 0
    else:
        for j in range(0, size-i+1):
            if s[j] != s[j+i-1] or dp[j+1][j+i-2] == 0:
                dp[j][j+i-1] = 0
            else:
                dp[j][j+i-1] = dp[j][int((j+j+i-2)/2)] + 1
                for p in range(1, dp[j][j+i-1]+1):
                    ans[p] += 1

for i in range(1, size):
    print(ans[i], end="")
    print(" ", end="")
print(ans[size])


s = input()
n = len(s)

dp = [[0 for i in range(n - le + 1)] for le in range(n + 1)]
ans = [0 for i in range(n + 1)]

for le in range(1, n + 1):
    for l in range(0, n - le + 1):
        r = l + le
        if s[l] != s[r - 1]:
            continue
        if le == 1:
            dp[1][l] = 1
            ans[1] += 1
        elif le == 2:
            ans[2] += 1
            dp[2][l] = 2
        elif dp[le - 2][l + 1]:
            v = 1
            m = (l + r) // 2
            st = m + 1 if le & 1 else m
            le2 = m - l
            q = dp[le2][l]
            if q:
                v = q + 1

            ans[v] += 1
            dp[le][l] = v


for i in range(n - 1, 0, -1):
    ans[i] += ans[i + 1]

print(*ans[1:])

s = input()

dp = [[0]*5005 for _ in range(5005)]
n = len(s)
ans = [0 for _ in range(5005)]

for length in range(1,n+1):
	for l in range(n-length+1):
		r = l+length
		if(length == 1):
			dp[l][r] = 1
			continue
		elif(length == 2):
			dp[l][r] = 2 if(s[l] == s[r-1]) else 0
			continue
		if(s[l] != s[r-1] or dp[l+1][r-1] == 0):
			continue
		dp[l][r] = 1
		m = (l+r) // 2
		if(length&1):
			if(dp[l][m] and dp[m+1][r]):
				dp[l][r] = dp[l][m]+1
		else:
			if(dp[l][m] and dp[m][r]):
				dp[l][r] = dp[l][m]+1

for length in range(1,n+1):
	for l in range(n-length+1):
		ans[dp[l][l+length]] += 1

for i in range(n-1,0,-1):
	ans[i] += ans[i+1]

for i in range(1,n+1):
	print(ans[i],end=' ')

print()


s = input()
n = len(s)
max_palin = [[0 for i in range(n + 1)] for j in range(n + 1)]
count = [0 for i in range(n + 1)]

for sub_len in range(1, n + 1):
    for left in range(0, n - sub_len + 1):
        right = left + sub_len - 1

        if sub_len == 1:
            max_palin[left][right] = 1
        elif sub_len == 2:
            if s[left] == s[right]:
                max_palin[left][right] = 2
            else:
                max_palin[left][right] = 0
        else:
            if s[left] == s[right] and max_palin[left + 1][right - 1] > 0:
                mid = (left + right) // 2

                if sub_len % 2 == 0:
                    max_palin[left][right] = max_palin[left][mid] + 1
                else:
                    max_palin[left][right] = max_palin[left][mid - 1] + 1

        count[max_palin[left][right]] += 1

for i in range(n - 1, 0, -1):
    count[i] += count[i + 1]

for i in range(1, n + 1):
    print(count[i], end=' ')

print()


s = input()
n = len(s)
max_palin = [[0 for i in range(n + 1)] for j in range(n + 1)]
count = [0 for i in range(n + 1)]

for sub_len in range(1, n + 1):
    for left in range(0, n - sub_len + 1):
        right = left + sub_len - 1

        if sub_len == 1:
            max_palin[left][right] = 1
        elif sub_len == 2:
            if s[left] == s[right]:
                max_palin[left][right] = 2
            else:
                max_palin[left][right] = 0
        else:
            if s[left] == s[right] and max_palin[left + 1][right - 1] > 0:
                max_palin[left][right] = max_palin[left][left + sub_len // 2 - 1] + 1

        count[max_palin[left][right]] += 1

for i in range(n - 1, 0, -1):
    count[i] += count[i + 1]

for i in range(1, n + 1):
    print(count[i], end=' ')

print()


P = 311
# we use two mods to reduce the chance of collision
MOD1 = int(1e9) + 7
MOD2 = int(1e9) + 9


def main():
    s = input()
    n = len(s)

    # Pre-compute
    power_1 = [0 for i in range(n + 1)]
    power_2 = [0 for i in range(n + 1)]
    mod_inv_1 = [0 for i in range(n + 1)]
    mod_inv_2 = [0 for i in range(n + 1)]
    power_1[0] = 1
    power_2[0] = 1
    mod_inv_1[0] = 1
    mod_inv_2[0] = 1

    for i in range(1, n + 1):
        power_1[i] = power_1[i - 1] * P % MOD1
        power_2[i] = power_2[i - 1] * P % MOD1
        mod_inv_1[i] = bin_exp(power_1[i], MOD1 - 2, MOD1)
        mod_inv_2[i] = bin_exp(power_2[i], MOD2 - 2, MOD2)

    # Compute hash values
    hash_1 = 0
    hash_2 = 0
    forward_hash_1 = [0 for i in range(n + 1)]
    forward_hash_2 = [0 for i in range(n + 1)]

    for i in range(1, n + 1):
        hash_1 += ord(s[i - 1]) * power_1[i]
        hash_2 += ord(s[i - 1]) * power_2[i]
        hash_1 %= MOD1
        hash_2 %= MOD2
        forward_hash_1[i] = hash_1
        forward_hash_2[i] = hash_2

    hash_1 = 0
    hash_2 = 0
    backward_hash_1 = [0 for i in range(n + 1)]
    backward_hash_2 = [0 for i in range(n + 1)]

    for i in range(1, n + 1):
        hash_1 += ord(s[n - i]) * power_1[i]
        hash_2 += ord(s[n - i]) * power_2[i]
        hash_1 %= MOD1
        hash_2 %= MOD2
        backward_hash_1[i] = hash_1
        backward_hash_2[i] = hash_2

    dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
    count = [0 for i in range(n + 1)]

    for sub_len in range(1, n + 1):
        for left in range(0, n - sub_len + 1):
            right = left + sub_len - 1

            if sub_len == 1:
                dp[left][right] = 1
            elif sub_len == 2:
                if s[left] == s[right]:
                    dp[left][right] = 2
            else:
                if s[left] == s[right] and dp[left + 1][right - 1] > 0:
                    dp[left][right] = dp[left][left + sub_len // 2 - 1] + 1

            count[dp[left][right]] += 1

    for i in range(n - 1, 0, -1):
        count[i] += count[i + 1]

    for i in range(1, n + 1):
        print(count[i], end=' ')

    print()


def bin_exp(a, x, mod):
    res = 1
    
    while x > 0:
        if x & 1:
            res *= a
            res %= mod
        a *= a 
        a %= mod 
        x >>= 1
    
    return res


def get_forward_hash(forward_hash, mod_inv, left, right, mod):
    return (forward_hash[right + 1] - forward_hash[left] + mod) * mod_inv[left] % mod


def get_backward_hash(backward_hash, mod_inv, n, left, right):
    r_left = n - left - 1
    r_right = n - right - 1
    return (backward_hash[r_left + 1] - backward_hash[r_right] + mod) * mod_inv[r_right] % mod


def __starting_point():
    main()
__starting_point()

def main():
    s = input()
    n = len(s)
    dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
    count = [0 for i in range(n + 1)]

    for sub_len in range(1, n + 1):
        for left in range(0, n - sub_len + 1):
            right = left + sub_len - 1

            if sub_len == 1:
                dp[left][right] = 1
            elif sub_len == 2:
                if s[left] == s[right]:
                    dp[left][right] = 2
            else:
                if s[left] == s[right] and dp[left + 1][right - 1] > 0:
                    dp[left][right] = dp[left][left + sub_len // 2 - 1] + 1

            count[dp[left][right]] += 1

    for i in range(n - 1, 0, -1):
        count[i] += count[i + 1]

    for i in range(1, n + 1):
        print(count[i], end=' ')

    print()


def __starting_point():
    main()
__starting_point()

class HString:
	def __init__(self, string, base=257, modulo=1000000007):
		self.__base, self.__modulo = base, modulo
		self.__prefix_hash, self.__base_pow, self.__size = [], [1], 0

		self += string
	
	def __add__(self, string):
		for ch in string:
			self.__base_pow.append((self.__base_pow[-1] * self.__base) % self.__modulo)
			if self.__size == 0: self.__prefix_hash.append(ord(ch))
			else: self.__prefix_hash.append((self.__prefix_hash[-1] * self.__base + ord(ch)) % self.__modulo)
			self.__size += 1
		return self
	
	def size(self): return self.__size

	def getModulo(self): return self.__modulo

	def getHashValue(self, st, en):
		value = self.__prefix_hash[en]
		if st > 0:
			value -= ((self.__prefix_hash[st-1] * self.__base_pow[en-st+1]) % self.__modulo)
			if value < 0: value += self.__modulo
		return value

def palindromic_characteristics(s):
	n, org, rev = len(s), HString(s), HString(s[::-1])
	palindrome_level = [[0 for _ in range(n)] for _ in range(n)]
	palindrome_level_count = [0 for _ in range(n + 1)]

	for i in range(n):
		for j in range(i, n):
			if org.getHashValue(i, j) == rev.getHashValue(n-1-j, n-1-i):
				mid = (i + j) // 2 + (i + j) % 2
				if i > mid-1: palindrome_level[i][j] = 1
				else: palindrome_level[i][j] = palindrome_level[i][mid-1] + 1
				palindrome_level_count[palindrome_level[i][j]] += 1
	
	for i in range(n-1, 0, -1): palindrome_level_count[i] += palindrome_level_count[i+1]
	return palindrome_level_count[1:]

s = input()
print(' '.join(map(str, palindromic_characteristics(s))))

class HString:
	def __init__(self, string, base=257, modulo=1000000007):
		self.__base, self.__modulo = base, modulo
		self.__prefix_hash, self.__base_pow, self.__size = [], [1], 0

		self += string
	
	def __add__(self, string):
		for ch in string:
			self.__base_pow.append((self.__base_pow[-1] * self.__base) % self.__modulo)
			if self.__size == 0: self.__prefix_hash.append(ord(ch))
			else: self.__prefix_hash.append((self.__prefix_hash[-1] * self.__base + ord(ch)) % self.__modulo)
			self.__size += 1
		return self
	
	def size(self): return self.__size

	def getModulo(self): return self.__modulo

	def getHashValue(self, st, en):
		value = self.__prefix_hash[en]
		if st > 0:
			value -= ((self.__prefix_hash[st-1] * self.__base_pow[en-st+1]) % self.__modulo)
			if value < 0: value += self.__modulo
		return value

def palindromic_characteristics(s):
	n, org, rev = len(s), HString(s), HString(s[::-1])
	palindrome_level = [[0 for _ in range(n)] for _ in range(n)]
	palindrome_level_count = [0 for _ in range(n + 1)]

	i, j = 0, 0
	while i < n:
		j = i
		while j < n:
			if org.getHashValue(i, j) == rev.getHashValue(n-1-j, n-1-i):
				mid = (i + j) // 2 + (i + j) % 2
				if i > mid-1: palindrome_level[i][j] = 1
				else: palindrome_level[i][j] = palindrome_level[i][mid-1] + 1
				palindrome_level_count[palindrome_level[i][j]] += 1
			j += 1
		i += 1
	
	for i in range(n-1, 0, -1): palindrome_level_count[i] += palindrome_level_count[i+1]
	return palindrome_level_count[1:]

s = input()
print(' '.join(map(str, palindromic_characteristics(s))))

class HString:
	def __init__(self, string, base=257, modulo=1000000007):
		self.__base, self.__modulo = base, modulo
		self.__prefix_hash, self.__base_pow, self.__size = [], [1], 0

		self += string
	
	def __add__(self, string):
		for ch in string:
			self.__base_pow.append((self.__base_pow[-1] * self.__base) % self.__modulo)
			if self.__size == 0: self.__prefix_hash.append(ord(ch))
			else: self.__prefix_hash.append((self.__prefix_hash[-1] * self.__base + ord(ch)) % self.__modulo)
			self.__size += 1
		return self
	
	def size(self): return self.__size

	def getModulo(self): return self.__modulo

	def getHashValue(self, st, en):
		value = self.__prefix_hash[en]
		if st > 0:
			value -= ((self.__prefix_hash[st-1] * self.__base_pow[en-st+1]) % self.__modulo)
			if value < 0: value += self.__modulo
		return value

s = input()
n, org, rev = len(s), HString(s), HString(s[::-1])
palindrome_level = [[0 for _ in range(n)] for _ in range(n)]
palindrome_level_count = [0 for _ in range(n + 1)]

for i in range(n):
	for j in range(i, n):
		if org.getHashValue(i, j) == rev.getHashValue(n-1-j, n-1-i):
			mid = (i + j) // 2 + (i + j) % 2
			if i > mid-1: palindrome_level[i][j] = 1
			else: palindrome_level[i][j] = palindrome_level[i][mid-1] + 1
			palindrome_level_count[palindrome_level[i][j]] += 1

for i in range(n-1, 0, -1): palindrome_level_count[i] += palindrome_level_count[i+1]

print(' '.join(map(str, palindrome_level_count[1:])))

def palindromic_characteristics(s):
	n = len(s)
	palindrome_level = [[0 for _ in range(n)] for _ in range(n)]
	palindrome_level_count = [0 for _ in range(n + 1)]

	for i in range(n):
		j = i
		while i >= 0 and j < n and s[i] == s[j]:
			palindrome_level[i][j] = 1
			i, j = i - 1, j + 1
	
	for i in range(n-1):
		j = i + 1
		while i >= 0 and j < n and s[i] == s[j]:
			palindrome_level[i][j] = 1
			i, j = i - 1, j + 1

	for i in range(n):
		for j in range(i, n):
			if palindrome_level[i][j] > 0:
				mid = (i + j) // 2 + (i + j) % 2
				if i <= mid-1: palindrome_level[i][j] = palindrome_level[i][mid-1] + 1

				palindrome_level_count[palindrome_level[i][j]] += 1
	
	for i in range(n-1, 0, -1): palindrome_level_count[i] += palindrome_level_count[i+1]
	return palindrome_level_count[1:]

s = input()
print(' '.join(map(str, palindromic_characteristics(s))))

def PanlidromicCharacteristics(string):
  n = len(string)
  res = [[0 for i in range (n)] for j in range (n)]
  count = [0 for i in range (n + 1)]
  # for i in range (n):
  #   res[i][i] = 1
  #   count[1] += 1
  
  for length in range (1, n + 1):
    for i in range (n-length + 1):
      j = i + length - 1
      if length == 1:
          res[i][j] = 1
      elif length == 2 and string[i] == string[j]:
          res[i][j] = 2
      elif string[i] == string[j] and res[i + 1][j - 1] > 0:
        res[i][j] = res[i][i + length//2 - 1]  + 1        
      count[res[i][j]] += 1
      
  # k-palindrome is also a (k - 1)-palindrome
  for i in range (len(count) - 1, 0, -1):
    count[i - 1] += count[i]
  for i in range (1, len(count)):
    print(count[i], end = " ")
  return 
  
string = input()
PanlidromicCharacteristics(string)