Cho xâu ~S~ gồm các chữ cái tiếng Anh in thường. Gọi ~f(S)~ là số lượng kí tự phân biệt của xâu ~S~. Ví dụ ~S =~ abccaaa, vậy ~f(S)=3~.

Với mỗi ~K~ có giá trị từ ~1~ đến ~f(S)~, hãy đếm số lượng xâu con ~X~ của ~S~ có ~f(X) = K~.

INPUT

Gồm một xâu ~S~ (có số lượng kí tự - kí hiệu là ~|S|~ không vượt quá ~10^6~).

OUTPUT

Gồm ~f(S)~ dòng, mỗi dòng là kết quả tương ứng khi ~K~ có giá trị từ ~1~ đến ~f(S)~.

SAMPLE INPUT

abba

SAMPLE OUTPUT

5
5

Các xâu con có ~1~ kí tự phân biệt là (xâu được gạch chân): ~\underline{a} \textit{bba}, \textit{a}\underline{b}\textit{ba}, \textit{ab}\underline{b}\textit{a}, \textit{abb}\underline{a}, \textit{a}\underline{bb}\textit{a}~

Các xâu con có ~2~ kí tự phân biệt là (xâu được gạch chân): ~\underline{ab}\textit{ba}, \underline{abb}\textit{a}, \underline{abba}, \textit{a}\underline{bba}, \textit{ab}\underline{ba}~

SUBTASKS

• Có ~40\%~ số test ứng với ~40\%~ số điểm thoả mãn: ~|S|\le 10^2~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm thoả mãn: ~|S|\le 2\times 10^3~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm thoả mãn: ~|S|\le 10^5~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc gì thêm.