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.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Solver {

	public static void main(String[] Args) throws NumberFormatException,
			IOException {
		new Solver().Run();
	}

	PrintWriter pw;
	StringTokenizer Stok;
	BufferedReader br;

	public String nextToken() throws IOException {
		while (Stok == null || !Stok.hasMoreTokens()) {
			Stok = new StringTokenizer(br.readLine());
		}
		return Stok.nextToken();
	}

	public int nextInt() throws NumberFormatException, IOException {
		return Integer.parseInt(nextToken());
	}

	public double nextDouble() throws NumberFormatException, IOException {
		return Double.parseDouble(nextToken());
	}

	public long nextLong() throws NumberFormatException, IOException {
		return Long.parseLong(nextToken());
	}

	final int size=26;
	int n;
	int[] mas;
	long[] result;
	
	void findRes(){
		long[] resPref=new long[size+1];
		for (int i=0; i<n; i++){
			long[] withoutLast=new long[size+1];
			int[] kolChars=new int[size];
			int curKol=0;
			int j=i-1;
			for (; j>=0 && mas[j]!=mas[i]; j--){
				if (kolChars[mas[j]]==0){
					curKol++;
				}
				kolChars[mas[j]]++;
				withoutLast[curKol]++;
			}
			withoutLast[0]=1;
			long[] nextPref=new long[size+1];
			for (int z=1; z<=size; z++){
				nextPref[z]+=(resPref[z]-withoutLast[z]);
			}
			for (int z=0; z<size; z++){
				nextPref[z+1]+=withoutLast[z];
			}
			for (int z=0; z<=size; z++){
				result[z]+=nextPref[z];
			}
			resPref=nextPref;
		}
	}
	
	public void Run() throws NumberFormatException, IOException {
		//br = new BufferedReader(new FileReader("input.txt")); pw = new PrintWriter("output.txt");
		br=new BufferedReader(new InputStreamReader(System.in));  pw=new PrintWriter(new OutputStreamWriter(System.out));
		
		String str=br.readLine();
		n=str.length();
		mas=new int[n];
		for (int i=0; i<n; i++){
			mas[i]=(int)str.charAt(i)-(int)'a';
		}
		result=new long[size+1];
		findRes();
		int i=1;
		int resSize=0;
		while (i<=size && result[i]>0)
			i++;
		resSize=i;
		pw.println(resSize-1);
		for (i=1; i<resSize; i++){
			pw.println(result[i]);
		}
		pw.flush();
		pw.close();
	}

}