Sətir blokları

Blok $S$ sətrinin $i$ mövqeyindəki ən böyük alt sətrini, həmin mövqedən başlayaraq prefiksi ilə üst-üstə düşən alt sətir kimi təyin edək. $0$ mövqeyindəki blokun uzunluğunu sıfır qəbul edəcəyik.

Sətrin $S$ bloklarının uzunluqlarını bütün mövqelər üçün hesablayın.

Giriş verilənləri

Yeganə sətir $S(|S|\le 10^6)$.

Çıxış verilənləri

Bir sətirdə $S$ sətrinin bütün mövqeləri üçün blokların uzunluqlarını göstərin.

Nümunələr