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 Main {
		private InputStream is;
		private PrintWriter out;
		int time = 0, DP[], start[], end[], dist[],  black[], MOD = (int)(1e9+9), arr[], weight[][], x[], y[], parent[];
		int MAX = 800000, N, K;
		long red[];
		ArrayList<Integer>[] amp;
		ArrayList<Pair>[][] pmp;
		boolean b[], boo[][];
		Pair prr[];
		HashMap<Integer,Long> hm[] = new HashMap[305];
		long Dp[][][][] = new long[110][110][12][12];
		void soln() {
			is = System.in;
			out = new PrintWriter(System.out);
			long s = System.currentTimeMillis();
			solve();
			//out.close();
			out.flush();
			//tr(System.currentTimeMillis() - s + "ms");
		}
		public static void main(String[] args) throws Exception {
			new Thread(null, new Runnable() {
			public void run() {
				try {
			//new CODEFORCES().soln();
			} catch (Exception e) {
					System.out.println(e);
				}
			}
		}, "1", 1 << 26).start();
			new Main().soln();
		}
		int ans = 0, cost = 0;
		char ch[], ch1[];
		int dp[][] = new int[5010][5010], n;
		int hash = 29;
		long h[] = new long[5050];
		int val[] = new int[5050];
		long r[] = new long[5050];
		int a[] = new int[5050];
		long see[] = new long[5050];
		void solve(){
			ch = ns().toCharArray();
			n = ch.length;
			for(int i = 0; i<n;i++){
				h[i] = ch[i] * power(hash,i,MOD);
				if(i>0) h[i] += h[i-1];
				h[i] %= MOD;
			}
			for(int i = 0;i<5050;i++){
				long temp = power(hash, i, MOD);
				r[i] = power(temp,MOD-2,MOD);
			}
			for(int i = 0;i<=5010;i++){
				int x = i;
				int cnt = 0;
				while(x>0){
					x/=2;
					cnt++;
				}
				val[i] = cnt;
			}
			for(int i = 0;i<5010;i++) for(int j = 0; j<5010;j++) dp[i][j] = -1;
			for(int i = 0;i<5005;i++){
				see[i] = power(hash,i,MOD);
			}
			recur(0,ch.length-1);
			for(int i = n-1;i>=0;i--) a[i] += a[i+1];
			for(int i = 1;i<=n;i++){
				out.print(a[i]+" ");
			}
			//System.out.println(dp[0][n-1]+" "+dp[0][4]);
			//System.out.println(check(5,7,6));
			//System.out.prinatln(check(5,7,6));
		}
		int recur(int i, int j){
			//System.out.println(i+" "+j);
			if(dp[i][j]!=-1){
				return dp[i][j];
			}
			dp[i][j] = -2;
			if(i==j){
				dp[i][j] = 1;
				a[1]++;
				return 1;
			}
			if(i>j){
				dp[i][j] = 1;
				return 1;
			}
			int mid = (i+j+1)/2;
			int b = 0;
			recur(i+1,j);
			recur(i,j-1);
			recur(i+1,j-1);
			b = recur(i,mid-1);
			if(b>-2 && check(i,j,mid)){
				a[b+1]++;
				dp[i][j] = b+1;
			}
			else if(ch[i]==ch[j]){
				if(dp[i+1][j-1]>=0){
					dp[i][j]= 1;
					a[1]++;
				}
			}
			return dp[i][j];
		}
		boolean check(int i, int j, int mid){
			long a1 = ((h[mid-1]-((i!=0)?h[i-1]:0))%MOD+10L*MOD)%MOD, a2  = ((h[j]-(((j-i)%2==0)?h[mid]:h[mid-1]))+10L*MOD)%MOD;
			long temp = r[i], temp2 = r[(((j-i)%2==0)?(mid+1):(mid))];
			//System.out.println(a1+" "+a2+" "+r[i]+" "+temp2);
			//System.out.println(a1+" "+a2);
			a1 = a1*temp;
			a1%=MOD;
			a2 = a2*temp2;
			a2%=MOD;
			//System.out.println(i+" "+j+" "+mid+" "+(a1==a2));
			return a1==a2;
		}
		void sieve(int n){
			b = new boolean[n+1];
			b[0] = b[1] = true;
			for(int i = 2;i*i<n;i++){
				if(!b[i]){
					for(int j = 2*i;j<100001;j+=i) b[j] = true;
				}
			}
		}
		class Pair implements Comparable<Pair>{
			int u, v, i;
			
			Pair(int u, int v){
				this.u = u;
				this.v = v;
			}
			Pair(){
				
			}
			Pair(int u, int v, int i){
				this.u = u;
				this.v = v;
				this.i = i;
			}
			public int hashCode() {
				return Objects.hash();
			}
			public boolean equals(Object o) {
				Pair other = (Pair) o;
				return ((u == other.u && v == other.v)); 
			}
			public int compareTo(Pair other) {
				//return Integer.compare(val, other.val);
				return Long.compare(u, other.u) != 0 ? (Long.compare(u, other.u)) : (Long.compare(v,other.v));
			}
			public String toString(){
				return this.u +" " + this.v;
			}
		}
		int max(int a, int b){
			if(a>b) return a;
			return b;
		}
		public static class FenwickTree {
			
		    int[] array; // 1-indexed array, In this array We save cumulative information to perform efficient range queries and updates
	 
		    public FenwickTree(int size) {
		        array = new int[size + 1];
		    }
		    public int rsq(int ind) {
		        assert ind > 0;
		        int sum = 0;
		        while (ind > 0) {
		            sum += array[ind];
		            //Extracting the portion up to the first significant one of the binary representation of 'ind' and decrementing ind by that number
		            ind -= ind & (-ind);
		        }
		        return sum;
		    }
		    public int rsq(int a, int b) {
		        assert b >= a && a > 0 && b > 0;
		        return rsq(b) - rsq(a - 1);
		    }
		    public void update(int ind, int value) {
		        assert ind > 0;
		        while (ind < array.length) {
		            array[ind] += value;
		            //Extracting the portion up to the first significant one of the binary representation of 'ind' and incrementing ind by that number
		            ind += ind & (-ind);
		        }
		    }
		    public int size() {
		        return array.length - 1;
		    }
		}
		void buildGraph(int n){
			for(int i = 0; i<n ;i++){
				int x1 = ni() -1, y1 = ni()-1;
				amp[x1].add(y1);
				amp[y1].add(x1);
				x[i] = x1; y[i] = y1;
			}
		}
		long modInverse(long a, long mOD2){
	        return  power(a, mOD2-2, mOD2);
		}
		long power(long x, long y, long m)
		{
			if (y == 0)
	    return 1;
		long p = power(x, y/2, m) % m;
		p = (p * p) % m;
	 
		return (y%2 == 0)? p : (x * p) % m;
		}
		public long gcd(long a, long b){
			if(b==0) return a;
			return gcd(b,a%b);
		}
		static class ST1{
			int arr[], st[], size;
			ST1(int a[]){
				arr = a.clone();
				size = 10*arr.length;
				st = new int[size];
				build(0,arr.length-1,1);
			}
			void build(int ss, int se, int si){
				if(ss==se){
					st[si] = arr[ss];
					return;
				}
				int mid = (ss+se)/2;
				int val = 2*si;
				build(ss,mid,val); build(mid+1,se,val+1);
				st[si] = Math.min(st[val], st[val+1]);
			}
			int get(int ss, int se, int l, int r, int si){
				if(l>se || r<ss || l>r) return Integer.MAX_VALUE;
				if(l<=ss && r>=se) return st[si];
				int mid = (ss+se)/2;
				int val = 2*si;
				return Math.min(get(ss,mid,l,r,val), get(mid+1,se,l,r,val+1));
			}
		}
		static class ST{
			int arr[],lazy[],n;
			ST(int a){
				n = a;
				arr = new int[10*n];
				lazy = new int[10*n];
			}
			void up(int l,int r,int val){
				update(0,n-1,0,l,r,val);
			}
			void update(int l,int r,int c,int x,int y,int val){
				if(lazy[c]!=0){
					lazy[2*c+1]+=lazy[c];
					lazy[2*c+2]+=lazy[c];
					if(l==r)
						arr[c]+=lazy[c];
					lazy[c] = 0;
				}
				if(l>r||x>y||l>y||x>r)
					return;
				if(x<=l&&y>=r){
					lazy[c]+=val;
					return ;
				}
				int mid = l+r>>1;
				update(l,mid,2*c+1,x,y,val);
				update(mid+1,r,2*c+2,x,y,val);
				arr[c] = Math.max(arr[2*c+1], arr[2*c+2]);
			}
			int an(int ind){
				return ans(0,n-1,0,ind);
			}
			int ans(int l,int r,int c,int ind){
				if(lazy[c]!=0){
					lazy[2*c+1]+=lazy[c];
					lazy[2*c+2]+=lazy[c];
					if(l==r)
						arr[c]+=lazy[c];
					lazy[c] = 0;
				}
				if(l==r)
					return arr[c];
				int mid = l+r>>1;
				if(mid>=ind)
					return ans(l,mid,2*c+1,ind);
				return ans(mid+1,r,2*c+2,ind);
			}
		}
		public static int[] shuffle(int[] a, Random gen){
			for(int i = 0, n = a.length;i < n;i++)
			{ 
				int ind = gen.nextInt(n-i)+i; 
				int d = a[i]; 
				a[i] = a[ind];
				a[ind] = d; 
			} 
		return a; 
		}
		long power(long x, long y, int mod){
			long ans = 1;
			while(y>0){
				if(y%2==0){
					x = (x*x)%mod;
					y/=2;
				}
				else{
					ans = (x*ans)%mod;
					y--;
				}
			}
			return ans;
		}
	 
	 
		// To Get Input
		// Some Buffer Methods
		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 boolean oj = System.getProperty("ONLINE_JUDGE") != null;
	 
		private void tr(Object... o) {
			if (!oj)
				System.out.println(Arrays.deepToString(o));
		}
	}