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.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.concurrent.ArrayBlockingQueue;


public class ProblemC {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		char[] c = in.next().toCharArray();
		int n = c.length;
		int[] s = new int[n];
		for (int i = 0 ; i < n ; i++) {
			s[i] = c[i] - 'a';
		}

		long[] ans = new long[27];
		int[] qchar = new int[n+26];
		int[] qpos = new int[n+26];
		int[] qnext = new int[n+26];
		int qtail = 0;
		int[] has = new int[26];
		Arrays.fill(has, -1);
		for (int i = n-1 ; i >= 0 ; i--) {
			int stat = 1<<s[i];
			int now = i;
			for (int j = qtail-1 ; j >= 0 ; ) {
				if ((stat & (1<<qchar[j])) == 0) {
					int len = qpos[j] - now;
					ans[Integer.bitCount(stat)] += len;
					stat |= 1<<qchar[j];	
					now = qpos[j];
				}
				
				int tj = qnext[j];
				while (tj >= 0 && qchar[tj] == -1) {
					tj = qnext[tj];
				}
				qnext[j] = tj;
				j = tj;
			}
			
			ans[Integer.bitCount(stat)] += (n - now);
			
			qchar[qtail] = s[i];
			qpos[qtail] = i;
			qnext[qtail] = qtail-1;
			int qp = has[s[i]];
			if (qp >= 0) {
				qchar[qp] = qpos[qp] = -1;
			}
			has[s[i]] = qtail;
			qtail++;
		}
		
		int max = 0;
		for (int i = 1 ; i <= 26 ; i++) {
			if (ans[i] >= 1) {
				max = i;
			}		
		}
		
		out.println(max);
		for (int i = 1 ; i <= max ; i++) {
			out.println(ans[i]);
		}
		out.flush();
	}
	
	public static void debug(Object... o) {
		System.err.println(Arrays.deepToString(o));
	}
}