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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;


public class C {
    
    static void compute(String s) {
        int sdiv=0;
        boolean[] c2b=new boolean[26];
        for (int i=0; i<s.length(); i++) {
            int c=s.charAt(i)-'a';
            c2b[c]=true;
        }
        for (int i=0; i<c2b.length; i++) {
            if(c2b[i]) {
                sdiv++;
            }
        }
        
        int sz=0;
        int[] 
                idx=new int[sdiv+1], 
                ch=new int[sdiv+1];
        
        long[] ret=new long[sdiv+1];
        
        int r=0;
        while(r<s.length()) {
            char c=s.charAt(r);
            if(sz>0&&ch[sz-1]==c) {
                idx[sz-1]=r;
            } else {
                idx[sz]=r; ch[sz++]=c;
            }
            
            for (int i=0; i+1<sz; i++) {
                if(ch[i]==c) {
                    //remove
                    System.arraycopy(idx, i+1, idx, i, sz-1-i);
                    System.arraycopy(ch,  i+1, ch,  i, sz-1-i);
                    sz--;
                }
            }

            for (int i=0; i<sz; i++) {
                int div=sz-i;
                int cnt=(i==0? idx[i]+1: idx[i]-idx[i-1]);
                ret[div]+=cnt;
            }
            
            r++;
        }
        
        System.out.println(sdiv);
        for (int i=1; i<=sdiv; i++) {
            System.out.println(ret[i]);
        }
    }

    
    
    static void run_stream(InputStream ins) throws IOException {
        BufferedReader r=new BufferedReader(new InputStreamReader(System.in));
        compute(r.readLine());    
    }

    public static void main(String[] args) throws IOException {
        run_stream(System.in);
    }

}