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 CF {

	Random rnd = new Random(123);
	
	String gen(int n) {
		char[]res = new char[n];
		for (int i =0; i < n; i++) {
			res[i] = (char) ('a' + rnd.nextInt(26));
		}
		return new String(res);
	}
	
	void solve() {
		String s = in.next();
		int MAX = 20;
		int n = s.length();
		int[][] diff = new int[MAX][n];
		for (int i = 0; i < n; i++)
			diff[0][i] = 1 << (s.charAt(i) - 'a');
		for (int j = 1; j < MAX; j++) {
			for (int i = 0; i < n; i++) {
				diff[j][i] = diff[j - 1][i];
				int next = i + (1 << (j - 1));
				if (next < n)
					diff[j][i] |= diff[j - 1][next];
			}
		}
		int max = Integer.bitCount(diff[MAX - 1][0]);
		out.println(max);
		long[] res = new long[max];
		for (int fr = 0;fr < n; fr++) {
			int nowFrom = fr;
			int nowDiff = diff[0][fr];
			while (true) {
				int fro = nowFrom;
				nowFrom++;
				for (int i = MAX - 1; i >= 0; i--) {
					if (nowFrom >= n) {
						nowFrom = n;
						break;
					}
					if ((diff[i][nowFrom] | nowDiff) == nowDiff) {
						nowFrom += 1 << i;
					}
					if (nowFrom >= n) {
						nowFrom = n;
						break;
					}
				}
				res[Integer.bitCount(nowDiff) - 1] += (nowFrom - fro);
				if (nowFrom == n)
					break;
				nowDiff |= diff[0][nowFrom];
			}
		}
		for (int i = 0; i < max; i++)
			out.println(res[i]);
	}

	FastScaner in;
	PrintWriter out;

	void run() {
		in = new FastScaner(System.in);
		out = new PrintWriter(System.out);

		solve();

		out.close();
	}

	void runWithFiles() {
		in = new FastScaner(new File("input.txt"));
		try {
			out = new PrintWriter(new File("output.txt"));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}

		solve();

		out.close();
	}

	public static void main(String[] args) {
		Locale.setDefault(Locale.US);
		new CF().run();
	}

	class FastScaner {
		BufferedReader br;
		StringTokenizer st;

		FastScaner(InputStream is) {
			br = new BufferedReader(new InputStreamReader(is));
		}

		FastScaner(File f) {
			try {
				br = new BufferedReader(new FileReader(f));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				String s = null;
				try {
					s = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (s == null)
					return null;
				st = new StringTokenizer(s);
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}
	}
}