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.*;
import java.util.*;

public class D {
	public D() {
		Scanner s = new Scanner();
		String str = s.next();
		
		int n = str.length();
		int[][] good = new int[n][n+1];
		int[] counts = new int[n];
		//all intervals of length 1
		for (int i = 0; i < n; i++) {
			good[i][i+1] = 1;
			counts[0]++;
		}
		
		//all intervals of length 2
		for (int i = 0; i + 1 < n; i++) {
			if (str.charAt(i) == str.charAt(i+1)){
				good[i][i+2] = 1;
				counts[0]++;
			}
		
		}
		
		
		
		//all intervals of size k
		for (int k = 3; k <= n; k++) {
			for (int i = 0; i + k - 1 < n; i++) {
				if (str.charAt(i) == str.charAt(i + k - 1) && good[i + 1][i + k - 1] == 1) {
					good[i][i + k] = 1;
					counts[0]++;
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		
//		for (int i = 0; i < n; i++) {
//			for (int j = i + 1; j <= n; j++) {
//				System.out.println(i + "-" + j + "  :  " + good[i][j]);
//			}
//		}
//		System.out.println();
		
		//for each degree
		for (int k = 2; k <= Math.log(n) / Math.log(2) + 2 && k < n; k++) {
		
			for (int i = 0; i < n; i++) {
				for (int j = i + 1; j <= n; j++) {
					int s1 = i;
					int e1 = i + (j - i)/2;
					
					int s2 = j - (j - i) / 2;
					int e2 = j;
				
					
					if (good[s1][e1] >= k-1 && good[s2][e2] >= k-1 && good[i][j] >= k-1) {
						good[i][j]++;
						counts[k-1]++;
//						System.err.println(i + " " + j);
//						System.err.println(s1 + " " + e1 + " " + s2 + " " + e2);
					}
				}
			}	
		}
		
//		for (int i = 0; i < n; i++) {
//			for (int j = i + 1; j <= n; j++) {
//				System.out.println(i + "-" + j + "  :  " + good[i][j]);
//			}
//		}
			
		for (int i = 0; i < counts.length; i++) {
			sb.append(counts[i] + " " );
		}	
		System.out.println(sb.toString().trim());
	}
	

	public static void main(String[] args) {
		new D();
	}

	public static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		public Scanner(Reader in) {
			br = new BufferedReader(in);
		}

		public Scanner() {
			this(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}
		String readNextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}

}