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

public class TestClass {
	InputStream stream;
	byte[] buf = new byte[1024];
	int curChar;
	int numChars;
	SpaceCharFilter filter;
	PrintWriter pw;

	long dp[][];
	String h;

	long pi[] = new long[5001];
	long mod = (int) 1e9 + 7;

	void cnt(int x, int y) {
		if (x > y)
			return;
		if (x == y) {
			dp[x][y] = 1;
			return;
		}
		if (dp[x][y] >= 0)
			return;
		int mid = 0;
		if ((y - x) % 2 == 0) {
			mid = x + (y - x) / 2 - 1;
			cnt(x, mid);
			cnt(mid + 2, y);
			long a1 = l.get(x, mid), a2 = l.get(mid + 2, y);
			if (a1 == a2 && dp[x][mid] != 0)
				dp[x][y] = dp[x][mid] + 1;
			else {
				int nm = h.length() - 1;
				a2 = rev.get(nm - y, nm - mid - 2);
				if (a1 == a2)
					dp[x][y] = 1;
				else
					dp[x][y] = 0;
			}
		} else {
			mid = x + (y - x) / 2;
			cnt(x, mid);
			cnt(mid + 1, y);
			long a1 = l.get(x, mid), a2 = l.get(mid + 1, y);
			if (a1 == a2 && dp[x][mid] != 0)
				dp[x][y] = dp[x][mid] + 1;
			else {
				int nm = h.length() - 1;
				a2 = rev.get(nm - y, nm - mid - 1);
				if (a1 == a2)
					dp[x][y] = 1;
				else
					dp[x][y] = 0;
			}
		}
	}

	class Hashing {
		String a;
		int n;
		long hash[];

		Hashing(String b) {
			a = b;
			n = a.length();
			hash = new long[n];
			hash[0] = a.charAt(0) + 1 - 'a';
			for (int i = 1; i < n; i++)
				hash[i] = (hash[i - 1] * 26 + a.charAt(i) + 1 - 'a') % mod;
		}

		long get(int x, int y) {
			if (x == 0)
				return hash[y];
			long ans = hash[y] + mod - ((hash[x - 1] * pi[y - x + 1]) % mod);
			return ans % mod;
		}

	}

	Hashing l, rev;

	void soln() {
		h = nLi();
		dp = new long[h.length()][h.length()];
		pi[0] = 1;
		for (int i = 1; i <= 5000; i++)
			pi[i] = (pi[i - 1] * 26) % mod;
		for (int i = 0; i < h.length(); i++)
			Arrays.fill(dp[i], -1);
		l = new Hashing(h);
		rev = new Hashing(new String(new StringBuilder(h).reverse()));
		long ap[] = new long[h.length() + 1];
		for (int i = 0; i < h.length(); i++) {
			for (int j = i; j < h.length(); j++) {
				cnt(i, j);
				ap[(int) dp[i][j]]++;
			}
		}
		for (int i = h.length() - 1; i >= 0; i--)
			ap[i] += ap[i + 1];
		for (int i = 1; i <= h.length(); i++)
			pw.print(ap[i] + " ");
	}

	void run() {
		stream = System.in;
		pw = new PrintWriter(System.out);
		soln();
		pw.flush();
		pw.close();
	}

	public static void main(String[] args) {

		new Thread(null, new Runnable() {
			public void run() {
				try {

					new TestClass().run();

				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		}, "1", 1 << 26).start();

	}

	boolean isWhitespace(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}

	int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	int nI() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	long nL() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	String nextToken() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	String nLi() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	int[] nIA(int n) {
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = nI();
		return arr;
	}

	long[] nLA(int n) {
		long[] arr = new long[n];
		for (int i = 0; i < n; i++)
			arr[i] = nL();
		return arr;
	}

	void pArray(int[] arr) {
		for (int i = 0; i < arr.length; i++)
			pw.print(arr[i] + " ");
		pw.println();
		return;
	}

	void pArray(long[] arr) {
		for (int i = 0; i < arr.length; i++)
			pw.print(arr[i] + " ");
		pw.println();
		return;
	}

	boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}

	private interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}