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.Arrays;

public class Main {

    private static final int MOD = 1000000007;
    private static final int intINF = Integer.MAX_VALUE;
    private static final long longINF = Long.MAX_VALUE;

    private static void solve() {
        String s = sc.nextLine();
        int len = s.length();
        int[][] u = new int[len][len];
        int[] ans = new int[len+1];
        boolean[] can1 = new boolean[len];
        Arrays.fill(can1,true);
        boolean[] can2 = new boolean[len];
        Arrays.fill(can2,true);
        for (int j=0;j<len;j++){
            for (int i=j;i+j-1<len;i++){
                if (i+j<len && can1[i]){
                    if (s.charAt(i+j)==s.charAt(i-j)){
                        u[i-j][i+j]=1;
                        if (j*2>0){
                            int l = u[i-j][i-1];
                            int r= u[i+1][i+j];
                            if (l==r){
                                u[i-j][i+j]=l+1;
                                for (int o=1;o<=l+1;o++)ans[o]++;
                            }else ans[1]++;
                        }else ans[1]++;
                    }else can1[i]=false;
                }
                if (j>0 && can2[i]){
                    if (s.charAt(i+j-1)==s.charAt(i-j)){
                        u[i-j][i+j-1]=1;
                        int l = u[i-j][i-1];
                        int r= u[i][i+j-1];
                        if (l==r){
                            u[i-j][i+j-1]=l+1;
                            for (int o=1;o<=l+1;o++)ans[o]++;
                        }else ans[1]++;
                    }else can2[i]=false;
                }
            }
        }
        for (int i=1;i<=len;i++)pw.print(ans[i]+" ");
    }

    //TEMPLATE

    private static myScanner sc;
    private static PrintWriter pw;

    private static final int numberOfTests = 1;

    private static final String nameOfInAndOutFile = "";
    private static final String fullNameInputFile = nameOfInAndOutFile + ".in";
    private static final String fullNameOutputFile = nameOfInAndOutFile + ".out";

    public static void main(String[] args) throws IOException {
        if (nameOfInAndOutFile.length() == 0) {
            setDefaultInAndOutPut();
        } else {
            setInAndOutPutFromFile();
        }
        for (int test = 1; test <= numberOfTests; test++) {
            solve();
            pw.flush();
        }

        pw.close();
    }

    private static void setDefaultInAndOutPut() {
        sc = new myScanner(new BufferedReader(new InputStreamReader(System.in)));
        pw = new PrintWriter(System.out);
    }

    private static void setInAndOutPutFromFile() throws IOException {
        sc = new myScanner(new BufferedReader(new FileReader(new File(fullNameInputFile))));
        pw = new PrintWriter(new File(fullNameOutputFile));
    }
}

class myScanner {
    private char[] buffer = new char[1 << 8];
    private int pos = 1;

    private BufferedReader reader;

    public myScanner(BufferedReader reader) {
        this.reader = reader;
    }

    public boolean hasNext() {
        return pos > 0;
    }

    private void loadBuffer() {
        pos = 0;
        try {
            for (int i; (i = reader.read()) != -1; ) {
                char c = (char) i;
                if (c != ' ' && c != '\n' && c != '\t' && c != '\r' && c != '\f') {
                    if (pos == buffer.length) buffer = Arrays.copyOf(buffer, 2 * pos);
                    buffer[pos++] = c;
                } else if (pos != 0) break;
            }
        } catch (IOException e) {
            throw new UncheckedIOException(e);
        }
    }

    public String current() {
        return String.copyValueOf(buffer, 0, pos);
    }


    public String next() {
        loadBuffer();
        return current();
    }


    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            throw new UncheckedIOException(e);
        }
    }


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

    public long nextLong() {
        return nextLong(10);
    }

    public int nextInt(int radix) {
        loadBuffer();
        int result = 0;
        int i = buffer[0] == '-' || buffer[0] == '+' ? 1 : 0;
        for (checkValidNumber(pos > i); i < pos; i++) {
            int digit = buffer[i] - '0';
            checkValidNumber(0 <= digit && digit <= radix - 1);
            result = result * radix + digit;
        }
        return buffer[0] == '-' ? -result : result;
    }

    public long nextLong(int radix) {
        loadBuffer();
        long result = 0;
        int i = buffer[0] == '-' || buffer[0] == '+' ? 1 : 0;
        for (checkValidNumber(pos > i); i < pos; i++) {
            int digit = buffer[i] - '0';
            checkValidNumber(0 <= digit && digit <= radix - 1);
            result = result * radix + digit;
        }
        return buffer[0] == '-' ? -result : result;
    }

    public int[] nextArrayInts(int size) {
        int[] input = new int[size];
        for (int i = 0; i < size; i++) input[i] = nextInt();
        return input;
    }

    public long[] nextArrayLongs(int size) {
        long[] input = new long[size];
        for (int i = 0; i < size; i++) input[i] = nextLong();
        return input;
    }

    public double nextDouble() {
        loadBuffer();
        long result = 0;
        int i = buffer[0] == '-' || buffer[0] == '+' ? 1 : 0;
        long round = 1;
        final int radix = 10;
        boolean hasPoint = false;
        for (checkValidNumber(pos > i); i < pos; i++) {
            int digit = buffer[i] - '0';
            checkValidNumber((0 <= digit && digit <= radix - 1) || (!hasPoint && digit == -2));
            if (digit == -2) hasPoint = true;
            else {
                if (hasPoint) round *= radix;
                result = result * radix + digit;
            }

        }
        return buffer[0] == '-' ? -result / (1.0 * round) : result / (1.0 * round);
    }

    private void checkValidNumber(boolean condition) {
        if (!condition) throw new NumberFormatException(current());
    }
}