Cho xâu ~S~ độ dài ~N ≤ 10^5~. Tính và đưa ra dãy ~t_1, t_2, ..., t_N~ với ~t_i~ là số lần xuất hiện của xâu ~S[1...i]~ trong xâu ~S~.

Input

• Gồm một dòng duy nhất chứa xâu ~S~ chỉ gồm các chữ cái Latin thường độ dài không vượt quá ~10^5~.

Output

• Một dòng duy nhất in ra các giá trị ~t_1, t_2, ..., t_N~ các nhau bởi một dấu cách trống.

Sample

Input #1

abababa

Output #1

4 3 3 2 2 1 1

Problem source: Kc97ble - Free Contest