Problem: String diversity is the number of symbols that occur in the string at least once. Diversity of s will be denoted by d(s). For example , d("aaa")=1, d("abacaba")=3.

Given a string s, consisting of lowercase Latin letters. Consider all its substrings. Obviously, any substring diversity is a number from 1 to d(s). Find statistics about substrings diversity: for each k from 1 to d(s), find how many substrings of s has a diversity of exactly k.

Input

The input consists of a single line containing s. It contains only lowercase Latin letters, the length of s is from 1 to 3·105.

Output

Print to the first line the value d(s). Print sequence t1, t2, ..., td(s) to the following lines, where ti is the number of substrings of s having diversity of exactly i.

Examples

Input

abca


Output

3
4
3
3


Input

aabacaabbad


Output

4
14
19
28
5

Note

Consider the first example.

We denote by s(i, j) a substring of "abca" with the indices in the segment [i, j].

  * s(1, 1) =  "a", d("a") = 1
  * s(2, 2) =  "b", d("b") = 1
  * s(3, 3) =  "c", d("c") = 1
  * s(4, 4) =  "a", d("a") = 1
  * s(1, 2) =  "ab", d("ab") = 2
  * s(2, 3) =  "bc", d("bc") = 2
  * s(3, 4) =  "ca", d("ca") = 2
  * s(1, 3) =  "abc", d("abc") = 3
  * s(2, 4) =  "bca", d("bca") = 3
  * s(1, 4) =  "abca", d("abca") = 3



Total number of substring with diversity 1 is 4, with diversity 2 equals 3, 3 diversity is 3.

Solution (in JAVA):

Solution:
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigDecimal;
import java.util.*;
import java.math.BigInteger;

import static java.lang.Math.*;
import static java.math.BigInteger.*;
import static java.util.Arrays.*;


public class Main{

    void run(){
        boolean oj = System.getProperty("ONLINE_JUDGE") != null;
//        boolean oj = true;
        try{
            if( oj ){
                sc  = new FastScanner( new InputStreamReader(System.in  ) );
                out = new PrintWriter(   new OutputStreamWriter(System.out) );
            } else{
                sc  = new FastScanner(new FileReader("in.txt") );
//                sc  = new FastScanner(new FileReader("D:\\JavaOlymp\\FatalError\\output.txt") );
                out = new PrintWriter(   new FileWriter("out.txt") );
            }
        } catch (Exception e) {
            System.exit(-1);
        }
        long tB = System.currentTimeMillis();
        solve();
        if( !oj ) System.err.println( "Time: " + (System.currentTimeMillis()-tB)/1e3 );
        out.flush();
    }

    class FastScanner{
        BufferedReader br;
        StringTokenizer st = new StringTokenizer("");
        FastScanner( InputStreamReader a ){
            br = new BufferedReader(a);
        }
        FastScanner( FileReader a ){
            br = new BufferedReader(a);
        }
        String next(){
            while( !st.hasMoreTokens() )
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    return null;
                }
            return st.nextToken();
        }
        String readLine(){
            try {
                return br.readLine();
            } catch (Exception e) {
                return null;
            }
        }
        int nextInt(){ return Integer.parseInt(next()); }
    }

    FastScanner sc;
    PrintWriter out;



    public static void main(String[] args){
        new Main().run();
//        new Thread( null, new Runnable() {
//            @Override
//            public void run() {
//                new Main().run();
//            }
//        }, "LOL", (long)1e18 ).run();
    }



    void TLE(){ for(;;); }

    void MLE(){
        int[][] adj = new int[1024*1024][];
        for( int i = 0; i < adj.length; ++i )
            adj[i] = new int[1024*1024];
    }

    void exit( int val ){
        out.flush();
        System.exit(val);
    }
    //////////////////////////////////////////////////////////////////////////////////////////

    int n;
    int[] s;
    int[][] pos;
    long[] ans = new long[100];

    void solve(){

        {
            char[] str = sc.next().toCharArray();
            s = new int[str.length];
            for( int i = 0; i < s.length; ++i ) s[i] = str[i] - 'a';
            n = s.length;
        }

        pos = new int[s.length][26];
        for( int[] i : pos ) fill( i, Integer.MAX_VALUE );
        for( int i = s.length-2; 0 <= i; --i ){
            for( int ch = 0; ch < 26; ++ch ){
                pos[i][ch] = pos[i+1][ch];
            }
            pos[i][s[i+1]] = i+1;
        }

        for( int i = 0; i < s.length; ++i ){
            boolean[] used = new boolean[26];
            for( int card = 1, l, r = i-1; ; ++card ){
                l = r + 1;
                r = n - 1;
                if( l == n ) break;
                used[s[l]] = true;

                int[] posl = pos[l];
                for( int ch = 0; ch < 26; ++ch )
                    if( !used[ch] )
                        r = min( r, pos[l][ch]-1 );
                ans[card] += r - l + 1;
//                out.printf( "l,r: %d %d\n", l, r );
            }
        }

        int ds = ans.length - 1;
        while( ans[ds]==0 ) --ds;
        out.println( ds );
        for( int i = 1; i <= ds; ++i ) out.println( ans[i] );
        /**/
    }









}