Cho một xâu có độ dài \(n\). Với mỗi \(l=1,2,...n\) hãy tìm số lượng xâu con khác nhau của xâu ban đầu có độ dài là \(l\).

Input

• Dòng đầu tiên và duy nhất của input chứa một xâu có độ dài \(n\), gồm các kí tự in thường a - z.

Output

• In ra \(n\) số, tương ứng với kết quả của mỗi độ dài \(l\).

Constraints

• \(1 \leq n \leq 10^5\)

Example

abab

2 2 2 1