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.IOException;
import java.util.Arrays;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Mahmoud Aladdin <aladdin3>
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskC {
    private static final int MAX_ALPHA = 26;

    public void solve(int testNumber, InputReader jin, PrintWriter jout) {
        String token = jin.token();
        int[] arr = new int[MAX_ALPHA];
        long[] res = new long[MAX_ALPHA + 1];
        Arrays.fill(arr, 0);
        int l = 0, r = 0, count = 0;
        for(int i = 1; i <= MAX_ALPHA; i++) {
            int cnt = l = r = 0;
            while(r < token.length() || l < r) {
                int next = 0;
                if(r < token.length()) next = token.charAt(r) - 'a';
                if(r >= token.length() || (arr[next] == 0 && cnt + 1 > i)) {
                    // Need to remove
                    int prev = token.charAt(l) - 'a';
                    arr[prev]--; l++;
                    if(arr[prev] == 0)
                        cnt--;
                } else {
                    if(arr[next] == 0) cnt++;
                    arr[next]++; r++;
                    if(l < r)
                        res[i] += (r - l);
                }
            }
            //jout.println(i + " " + res[i] + " " + res[i - 1]);
            if(res[i] > res[i - 1]) count++;
        }
        jout.println(count);
        for(int i = 1; i <= count; i++) {
            jout.println(res[i] - res[i - 1]);
        }
    }
}

class InputReader {
    private static final int bufferMaxLength = 1024;
    private InputStream in;
    private byte[] buffer;
    private int currentBufferSize;
    private int currentBufferTop;
    private static final String tokenizers = " \t\r\f\n";
    
    public InputReader(InputStream stream) {
        this.in = stream;
        buffer = new byte[bufferMaxLength];
        currentBufferSize = 0;
        currentBufferTop = 0;
    }
    
    private boolean refill() {
        try {
            this.currentBufferSize = this.in.read(this.buffer);
            this.currentBufferTop = 0;
        } catch(Exception e) {}
        return this.currentBufferSize > 0;
    }
    
    
    private Byte readChar() {
        if(currentBufferTop < currentBufferSize) {
            return this.buffer[this.currentBufferTop++];
        } else {
            if(!this.refill()) {
                return null;
            } else {
                return readChar();
            }
        }
    }

    public String token()  {
        StringBuffer tok = new StringBuffer();
        Byte first;
        while((first = readChar()) != null && (tokenizers.indexOf((char) first.byteValue()) != -1));
        if(first == null) return null;
        tok.append((char)first.byteValue());
        while((first = readChar()) != null && (tokenizers.indexOf((char) first.byteValue()) == -1)) {
            tok.append((char)first.byteValue());
        }
        return tok.toString();
    }
    
    }