Weird Family Reunion

Points: 100
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
C, C++, Java, Python

In a family reunion, many families were invited.

Let's say n people come to the union. Every family_name can be represented as a English lowercase alphabet.

Example: aba

• $$1^{st}$$ guest is of family a
• $$2^{nd}$$ guest is of family b
• $$3^{rd}$$ guest is of family a

Conditions for sitting arrangements

• every member of a Family should sit on the same table
• To avoid conflicts between any two families, you want the number of people sitting on a table as minimum as possible

Table 1 will contain guests from 1 to $$x_1$$

Table 2 will contain guests from $$x_1 + 1$$ to $$x_2$$

Table 3 will contain guests from $$x_2 + 1$$ to $$x_3$$

and so on..

You need to find the number of Tables satisfying the conditions, and number of guests on each table.

See Example for more clarification

Input

a string S consisting of lowercase English alphabets

Output

The first line contains an integer n, number of tables The next line contains n space-separated integers, $$g_1, g_2, ..., g_n$$ where $$g_i$$ represents number of guests on Table $$i$$

Constraints

1 $$\leq$$ S.length $$\leq$$ 500

Example

Input

abacaddeghe

Output

3
5 2 4

Explanation

Table-1 consists of Family a, b and c

Table-2 consists of Family d

Table-3 consists of Family e, g and h

As we can see all the members of family a are on same table and similarly for all other family as well.

If we keep all guests on same table, condition 1 will satisfy but condition 2 will fail (minimum number of guests on a table)