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.IOException;
import java.io.InputStream;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Random;


public class Main {
  public static void main(String[] args) {
    FastScanner sc = new FastScanner();
    char[] s = sc.next().toCharArray();
//    char[] s = new char[5000];
//    for (int i = 0; i < s.length; i ++) {
//      s[i] = 'a';
//    }


    int n = s.length;
    int[][] dp = new int[n][n + 1];
    for (int[] v : dp) Arrays.fill(v, -1);
    
    RollingHashFactory rhf = new RollingHashFactory(2, 10000, new Random());

    RollingHash rh = new RollingHash(10000, rhf);
    for (char c : s) {
      rh.add(c);
    }
    for (int i = n - 1; i >= 0; i --) {
      rh.add(s[i]);
    }

    long[] count = new long[n];
    for (int left = 0; left < n; left ++) {
      for (int right = left + 1; right <= n; right ++) {
        int x = dfs(left, right, s, dp, rh);
        if (x > 0) {
          count[x - 1] ++;
        }
      }
    }
    
    
    for (int i = n - 1; i >= 1 ; i --) {
      count[i - 1] += count[i];
    }
    
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i ++) {
      sb.append(count[i]);
      sb.append(" ");
    }
    System.out.println(sb.substring(0, sb.length() - 1));

  }

  
  //[left, right)
  private static int dfs(int left, int right, char[] s, int[][] dp, RollingHash rh) {
    if (dp[left][right] >= 0) {
      return dp[left][right];
    }

    int tlen = right - left;
    if (tlen == 0) {
      dp[left][right] = 0;
      return 0;
    } else if (tlen == 1) {
      dp[left][right] = 1;
      return 1;
    }

    int len = (right - left) / 2;

    int nl1 = left;
    int nr1 = left + len;
    int nl2 = right - len;
    int nr2 = right;
    
//    boolean same = true;
//    for (int i = 0; i < len; i ++) {
//      if (s[nl1 + i] != s[nl2 + (len - i - 1)]) {
//        same = false;
//        break;
//      }
//    }
    boolean same = Arrays.equals(rh.query(nl1, nr1), rh.query(s.length + s.length - nr2, s.length + s.length - nl2));
    
    int ret;
    if (!same) {
      ret = 0;
    } else {
      int v = dfs(nl1, nr1, s, dp, rh);
      ret = v + 1;
    }
    dp[left][right] = ret;
    return ret;
  }
}

class RollingHash
{
    public RollingHashFactory rhf;
    public long[][] buf;
    public int p;
    
    public RollingHash(int bufsize, RollingHashFactory rhf)
    {
        buf = new long[rhf.deg][bufsize+1];
        this.rhf = rhf;
        this.p = 1;
    }
    
    public void add(int c)
    {
        for(int i = 0;i < rhf.deg;i++)buf[i][p] = (buf[i][p-1]*rhf.muls[i]+c)%rhf.mods[i];
        p++;
    }
    
    public void addr(int c)
    {
        for(int i = 0;i < rhf.deg;i++)buf[i][p] = (buf[i][p-1]+rhf.powers[i][p-1]*c)%rhf.mods[i];
        p++;
    }
    
    public long queryTwin(int r)
    {
        return buf[0][r]<<32|buf[1][r];
    }
    
    public long queryTwin(int l, int r)
    {
        assert l > r;
        assert rhf.deg == 2;
        long h = 0;
        for(int i = 0;i < rhf.deg;i++){
            long v = (buf[i][r] - buf[i][l] * rhf.powers[i][r-l]) % rhf.mods[i];
            if(v < 0)v += rhf.mods[i];
            h = h<<32|v;
        }
        return h;
    }
    
    public long[] query(int l, int r)
    {
        assert l > r;
        long[] h = new long[rhf.deg];
        for(int i = 0;i < rhf.deg;i++){
            h[i] = (buf[i][r] - buf[i][l] * rhf.powers[i][r-l]) % rhf.mods[i];
            if(h[i] < 0)h[i] += rhf.mods[i];
        }
        return h;
    }
}

class RollingHashFactory
{
    public int[] mods;
    public int[] muls;
    public long[][] powers;
    public int deg;
    
    public RollingHashFactory(int deg, int n, Random gen)
    {
        this.deg = deg;
        mods = new int[deg];
        muls = new int[deg];
        for(int i = 0;i < deg;i++){
            mods[i] = BigInteger.probablePrime(30, gen).intValue();
            muls[i] = BigInteger.probablePrime(30, gen).intValue();
        }
        powers = new long[deg][n+1];
        for(int i = 0;i < deg;i++){
            powers[i][0] = 1;
            for(int j = 1;j <= n;j++){
                powers[i][j] = powers[i][j-1] * muls[i] % mods[i];
            }
        }
    }
}

class FastScanner {
	public static String debug = null;

	private final InputStream in = System.in;
	private int ptr = 0;
	private int buflen = 0;
	private byte[] buffer = new byte[1024];
	private boolean eos = false;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				if (debug != null) {
					buflen = debug.length();
					buffer = debug.getBytes();
					debug = "";
					eos = true;
				} else {
					buflen = in.read(buffer);
				}
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen < 0) {
				eos = true;
				return false;
			} else if (buflen == 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	private void skipUnprintable() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
	}

	public boolean isEOS() {
		return this.eos;
	}

	public boolean hasNext() {
		skipUnprintable();
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		return (int) nextLong();
	}

	public long[] nextLongList(int n) {
		return nextLongTable(1, n)[0];
	}

	public int[] nextIntList(int n) {
		return nextIntTable(1, n)[0];
	}

	public long[][] nextLongTable(int n, int m) {
		long[][] ret = new long[n][m];
		for (int i = 0; i < n; i ++) {
			for (int j = 0; j < m; j ++) {
				ret[i][j] = nextLong();
			}
		}
		return ret;
	}

	public int[][] nextIntTable(int n, int m) {
		int[][] ret = new int[n][m];
		for (int i = 0; i < n; i ++) {
			for (int j = 0; j < m; j ++) {
				ret[i][j] = nextInt();
			}
		}
		return ret;
	}
}