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.util.*;

public class C {
    public static void main(String[] args) throws Exception {
        new C().solve();
    }

    void solve() throws IOException {
        InputReader in = new InputReader(System.in);

        String str = in.next();

        int[][] cidxList = new int[26][str.length()];
        int[] csize = new int[26];
        for (int i = 0; i < str.length(); i++) {
            int jj = str.charAt(i) - 'a';
            cidxList[jj][csize[jj]++] = i;
        }
        int[] cidx = new int[26];

        long[] ret = new long[26];
        int[] tmp = new int[26];
        int INF = Integer.MAX_VALUE / 2;
        for (int i = 0; i < str.length(); i++) {
            for (int jj = 0; jj < 26; jj++) {
                if (cidx[jj] < csize[jj]) {
                    tmp[jj] = cidxList[jj][cidx[jj]];
                } else {
                    tmp[jj] = INF;
                }
            }
            Arrays.sort(tmp);
            for (int jj = 0; jj < tmp.length && tmp[jj] != INF; jj++) {
                if (jj + 1 < tmp.length && tmp[jj + 1] != INF) {
                    ret[jj] += tmp[jj + 1] - tmp[jj];
                } else {
                    ret[jj] += str.length() - tmp[jj];
                }
            }

            cidx[str.charAt(i) - 'a']++;
        }

        int ds = 0;
        while (ds < 26 && ret[ds] != 0) {
            ds++;
        }

        System.out.println(ds);
        for (int i = 0; i < ds; i++) {
            System.out.println(ret[i]);
        }
    }
}

class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private StringBuilder sb = new StringBuilder();

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1) throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0) return -1;
        }
        return buf[curChar++];
    }

    public String next() {
        int c = read();
        while (isWhitespace(c)) {
            c = read();
        }
        sb.setLength(0);
        do {
            sb.appendCodePoint(c);
            c = read();
        } while (!isWhitespace(c));
        return sb.toString();
    }

    public int nextInt() {
        return (int) nextLong();
    }
    public long nextLong() {
        int c = read();
        while (isWhitespace(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9') throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isWhitespace(c));
        return res * sgn;
    }

    public static boolean isWhitespace(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

}

//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//