Cho một chuỗi \(S\) gồm các chữ cái in thường. Hãy chia chuỗi thành nhiều đoạn nhất có thể, sao cho mỗi chữ cái chỉ xuất hiện trong duy nhất một đoạn.

In ra độ dài của từng đoạn theo thứ tự từ trái sang phải.

Dữ liệu vào

• Một dòng chứa chuỗi \(S\) (độ dài \(1 \le |S| \le 10^5\)).

Kết quả ra

• In ra các số nguyên là độ dài các đoạn, phân cách bởi dấu cách.

Ví dụ

Input

abacdfegeh

Output

5 5