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 JAVA):

Solution:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class D {
	
	static int n;
	static String s;
	static boolean[][] isPal, isE, isES;
	static int[] ans;
	
	static void apply(int i, int l, int c) {	
		ans[c]++;
		if(2 * l <= n && isE[i][l]) 
			apply(i, 2 * l, c + 1);
		if(2 * l < n && isES[i][l])
			apply(i, 2 * l + 1, c + 1);
	}
	
	static int[] prefixFunction(char[] s)		// O(n)
	{
		int n = s.length, pi[] = new int[n];
		for(int i = 1, j = 0; i < n; ++i)		//j = pi[i-1] at the beginning of every iteration
		{
			while(j > 0 && s[i] != s[j])
				j = pi[j-1];
			if(s[i] == s[j])
				++j;
			pi[i] = j;
		}
		return pi;
	}
	
	static int[] zAlgo(char[] s)
	{
		int n = s.length;
		int[] z = new int[n];
		for(int i = 1, l = 0, r = 0; i < n; ++i)
		{
			if(i <= r)
				z[i] = Math.min(r - i + 1, z[i - l]);
			while(i + z[i] < n && s[z[i]] == s[i + z[i]])
				++z[i];
			if(i + z[i] - 1 > r)
				r = i + z[l = i] - 1;
		}
		return z;
}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		s = sc.next();
		n = s.length();
		
		isPal = new boolean[n][n + 1];
		isE = new boolean[n][n + 1];
		isES = new boolean[n][n + 1];
		for (int i = 0; i < s.length(); i++) {
			char[] tmp = new char[(n - i) * 2 + 1];
			int p = 0;
			for (int j = i; j < n; j++) {
				tmp[p] = tmp[tmp.length - p - 1] = s.charAt(j);
				p++;
			}
			tmp[p] = '$';
			
			int[] kmp = prefixFunction(tmp);
			int v = kmp[kmp.length - 1];
			while(v > 0) {
				isPal[i][v] = true;
				v = kmp[v - 1];
			}
		}
		
		for (int i = 0; i < n; i++) {
			char[] tmp = s.substring(i).toCharArray();
			int[] z = zAlgo(tmp);
			for (int j = 1; j < z.length; j++) {
				if(z[j] >= j)
					isE[i][j] = true;
				if(z[j] >= j - 1 && j > 1)
					isES[i][j - 1] = true;
			}
		}
		
		
		ans = new int[n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= n; j++) {
				if(!isPal[i][j])
					continue;
				ans[0]++;
				if(2 * j <= n && isE[i][j])
					apply(i, 2 * j, 1);
				if(2 * j + 1 <= n && isES[i][j])
					apply(i, 2 * j + 1, 1);
			}
		}

		for (int i = 0; i < n; i++) 
			out.print(ans[i] + " ");
		out.println();
		out.flush();
	}


	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while(st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}
	}

}