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:
/**
 * DA-IICT
 * Author : Savaliya Sagar
 */
import java.io.*;
import java.math.*;
import java.util.*;

import static java.util.Arrays.fill;
import static java.lang.Math.*;
import static java.util.Arrays.sort;
import static java.util.Collections.sort;

public class D835 {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	void solve() {
		char c[] = ns().toCharArray();
		int n = c.length;
		int dp[][] = new int[n][n];
		int pal[][] = new int[n][n];
		for(int i=0;i<n;i++)
		{
			dp[i][i] = 1;
			pal[i][i] = 1;
		}
		for(int i=0;i<n-1;i++)
		{
			if(c[i]==c[i+1])
			pal[i][i+1] = 1;
		}
	     int ans[] = new int[n+1];
	     ans[1]+=n;
	     for(int i=2;i<n;i++){
	    	 for(int j=0;j+i<n;j++){
	    		 if(pal[j+1][j+i-1]==1 && c[j]==c[j+i]){
	    			 pal[j][j+i] = 1;
	    		 }
	    	 }
	     }
		for(int l=1;l<n;l++){
			for(int i=0;i+l<n;i++){
				int l1 = i;
				int r1 = i+(l+1)/2 - 1;
				int l2 = i+(l+1)/2;
				if(l%2==0)
					l2++;
				int r2 = i+l;
				if(pal[i][i+l]==1){
					dp[i][i+l] = min(dp[l1][r1],dp[l2][r2])+1;
				}
				ans[dp[i][i+l]]++;
			}
		}
		for(int i=n-1;i>=0;i--)
			ans[i] += ans[i+1];
		for(int i=1;i<=n;i++){
			out.print(ans[i] + " ");
		}
	}
	


	
	 class Pair implements Comparable<Pair> {
	        long u;
	        long v;
	        public Pair(long u, long v) {
	            this.u = u;
	            this.v = v;
	        }


	        public int hashCode() {
	            int hu = (int) (u ^ (u >>> 32));
	            int hv = (int) (v ^ (v >>> 32));
	            return 31 * hu + hv;
	        }

	        public boolean equals(Object o) {
	            Pair other = (Pair) o;
	            return u == other.u && v == other.v;
	        }

	        public int compareTo(Pair other) {
	            return Long.compare(u, other.u) != 0 ? Long.compare(u, other.u) : Long.compare(v, other.v);
	        }

	        public String toString() {
	            return "[u=" + u + ", v=" + v + "]";
	        }
	    }


	void run() throws Exception {
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);

		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if (!INPUT.isEmpty())
			tr(System.currentTimeMillis() - s + "ms");
	}

	public static void main(String[] args) throws Exception {
		new Thread(null, new Runnable() {
			public void run() {
				try {
					new D835().run();
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		}, "1", 1 << 26).start();
	}

	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;

	private int readByte() {
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) {
			ptrbuf = 0;
			try {
				lenbuf = is.read(inbuf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}

	private boolean isSpaceChar(int c) {
		return !(c >= 33 && c <= 126);
	}

	private int skip() {
		int b;
		while ((b = readByte()) != -1 && isSpaceChar(b))
			;
		return b;
	}

	private double nd() {
		return Double.parseDouble(ns());
	}

	private char nc() {
		return (char) skip();
	}

	private String ns() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b !=
										// ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	private char[] ns(int n) {
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(isSpaceChar(b))) {
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}

	private char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = ns(m);
		return map;
	}

	private int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}

	private int ni() {
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private long nl() {
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private void tr(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}
}