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.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class c15 {

    static String s;
    static long last[];
    static long res[]; 
    static long max=0;
    static long LE[];
    public static void main(String[] args)throws Exception {
     s=str();
     last=new long [26];
     Arrays.fill(last, -1);
     res=new long [27];
     LE=new long [27];
     for (int i=0;i<s.length();i++){
         char c=s.charAt(i);
         max+=edit(c,i)?1:0;
         last[c-'a']=i;
     }
     System.out.println(max);
     for (int i=1;i<27;i++)if (res[i]==0)break;else System.out.println(res[i]);
     
    }
    private static boolean edit(char c,int k) {
        //System.out.println(c+"-->"+k+"-->"+last[c-'a']);
         long t[]=new long [27];
         if (last[c-'a']==-1){
             t[1]=1;
             res[1]++;
             for (int i=1;i<27;i++){
                 if (LE[i]!=0){
                     res[i+1]+=LE[i];
                     t[i+1]=LE[i];
                 }
             }
             LE=t;
            // pr(LE);
             return true;
         }
         else {
             boolean x=false;
             t[1]=1;
             res[1]++;
             long v=0;
             for (int i=1;i<27;i++){
                 if (LE[i]!=0){
                     if (k-(v+LE[i])<=last[c-'a'])x=true;
                     if (x==false){
                     res[i+1]+=LE[i];
                     t[i+1]+=LE[i];
                     v+=LE[i];
                     }
                     else{
                         res[i]+=LE[i];
                         t[i]+=LE[i];
                     }
                 }
             }
             LE=t;
            // pr(LE);
             return false;
             
         }
        
    } 
    static void pr(int [] a){
        for (int i=1;i<a.length;i++)if (a[i]==0)break;else System.out.print(a[i]+" ");
        System.out.println();
    }
    static BufferedReader buf=new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int in() throws IOException{
        if (st==null || !st.hasMoreTokens()){
            st=new StringTokenizer(buf.readLine());
        }
        return Integer.parseInt(st.nextToken());
    }
    static long ll() throws IOException{
        if (st==null || !st.hasMoreTokens()){
            st=new StringTokenizer(buf.readLine());
        }
        return Long.parseLong(st.nextToken());
    }
    static String str() throws IOException{
        if (st==null || !st.hasMoreTokens()){
            st=new StringTokenizer(buf.readLine());
        }
        return (st.nextToken());
    }
        static double dub() throws IOException{
            if (st==null || !st.hasMoreTokens()){
                st=new StringTokenizer(buf.readLine());
            }
            return Double.parseDouble(st.nextToken());
    }
}