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

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

class TaskC {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
                String s = in.nextToken();
                int n = s.length();
                int[][] next = new int[n][26];
                for (char c = 'a'; c <= 'z'; c++) {
                        int last = n;
                        for (int i = n - 1; i >= 0; i--)   {
                                if (s.charAt(i) == c)
                                        last = i;
                                next[i][c - 'a'] = last;
                        }
                }
                long[] cnt = new long[27];
                for (int i = 0; i < n; i++) {
                        int[] pos = new int[26];
                        for (int j = 0; j < 26; j++)
                                pos[j] = next[i][j];
                        ArrayUtils.sort(pos);
                        for (int c = 0; c < pos.length; c++) {
                                int last = c == pos.length - 1 ? n : pos[c + 1]; 
                                cnt[c + 1] += last - pos[c];
                        }
                }
                int max = 26;
                while (cnt[max] == 0)
                        max--;
                out.println(max);
                for (int i = 1; i <= max; i++)
                        out.println(cnt[i]);
        }
}

class FastScanner {
        BufferedReader reader;
        StringTokenizer tokenizer;

        public FastScanner(InputStream inputStream)  {
                reader = new BufferedReader(new InputStreamReader(inputStream));
        }

        public String nextToken() {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                        String line;
                        try {
                                line = reader.readLine();
                        } catch (IOException e) {
                                return null;
                        }
                        tokenizer = new StringTokenizer(line);
                }
                return tokenizer.nextToken();
        }

        }

class ArrayUtils {


        private static int[] intBuffer;

        public static void sort(int[] array) {
                if (array.length == 0)
                        return;
                intBuffer = new int[array.length];
                mergeSort(array, 0, array.length - 1);
        }

        private static void mergeSort(int[] array, int low, int high) {
                if (low == high)
                        return;
                int middle = (low + high) / 2;
                mergeSort(array, low, middle);
                mergeSort(array, middle + 1, high);
                merge(array, low, middle + 1, middle + 1, high + 1);
        }

        private static void merge(int[] array, int first1, int last1, int first2, int last2) {
                int start = first1;
                int pos = 0;
                while (first1 < last1 || first2 < last2) {
                        if (first1 < last1 && (first2 == last2 || array[first1] <= array[first2]))
                                intBuffer[pos++] = array[first1++];
                        else
                                intBuffer[pos++] = array[first2++];
                }
                System.arraycopy(intBuffer, 0, array, start, pos);
        }


        }