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 javax.swing.event.ListDataEvent;
import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class J implements Runnable {

    private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;

    private BufferedReader in;
    private PrintWriter out;
    private StringTokenizer tok = new StringTokenizer("");

    private void init() throws FileNotFoundException {
        Locale.setDefault(Locale.US);
        String fileName = "";
        if (ONLINE_JUDGE && fileName.isEmpty()) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        } else {
            if (fileName.isEmpty()) {
                in = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            } else {
                in = new BufferedReader(new FileReader(fileName + ".in"));
                out = new PrintWriter(fileName + ".out");
            }
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());

        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    int[] readIntArray(int size) throws IOException {
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = readInt();
        }
        return a;
    }

    public static void main(String[] args) {
        //new Thread(null, new _Solution(), "", 128 * (1L << 20)).start();
        new J().run();
    }

    long timeBegin, timeEnd;

    void time() {
        timeEnd = System.currentTimeMillis();
        System.err.println("Time = " + (timeEnd - timeBegin));
    }

    @Override
    public void run() {
        try {
            timeBegin = System.currentTimeMillis();
            init();
            solve();
            out.close();
            time();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(-1);
        }
    }

    class Window {
        int[] count = new int[26];
        int size;

        void add(char x) {
            count[x - 'a']++;
            if (count[x - 'a'] == 1) size++;
        }

        void remove(char x) {
            count[x - 'a']--;
            if (count[x - 'a'] == 0) size--;
        }
    }

    void solve() throws IOException {
        char[] a = readString().toCharArray();
        int[] left = new int[a.length];
        int[] right = new int[a.length];
        List<Long> res = new ArrayList<>();
        for (int len = 1; len <= 26; len++) {
            Arrays.fill(left, -1);
            Arrays.fill(right, -1);
            int r_ptr = 0;

            Window w1 = new Window();
            for (int i = 0; i < a.length; i++) {
                if (w1.size < len) {
                    while (r_ptr < a.length) {
                        w1.add(a[r_ptr++]);
                        if (w1.size == len) break;
                    }
                }
                if (w1.size == len) {
                    left[i] = r_ptr - 1;
                }
                w1.remove(a[i]);
            }
            Window w2 = new Window();
            r_ptr = 0;
            for (int i = 0; i < a.length; i++) {
                while (r_ptr < a.length) {
                    w2.add(a[r_ptr++]);
                    if (w2.size > len) {
                        r_ptr--;
                        w2.remove(a[r_ptr]);
                        break;
                    }
                }
                if (w2.size == len) {
                    right[i] = r_ptr - 1;
                }
                w2.remove(a[i]);
            }
            long answer = 0;
            for (int i = 0; i < a.length; i++) {
                if (left[i] == -1 || right[i] == -1) continue;
                answer += right[i] - left[i] + 1;
            }
            if (answer == 0) break;
            res.add(answer);
        }
        out.println(res.size());
        for (long x : res) {
            out.println(x);
        }
    }

//    int count(String s, int len) {
//        int ans = 0;
//        for (int i=)
//    }


}