For every prefix of the given string, determine whether it is possible to split it into 1, 2, 3, 4, 5, …, 31 non-empty palindromes.

The input contains a line of n lowercase Latin letters (1 ≤ n ≤ 300 000).

Print n non-negative integer numbers separated by line breaks. The i-th line should contain a decimal number. If you consider the binary representation of this decimal number, its digit on position (j − 1) must be equal to one if the prefix of length i can be split into j palindromes, and zero otherwise.

1₁₀ = 1₂; 2₁₀ = 10₂; 5₁₀ = 101₂; 14₁₀ = 1110₂; abaa = aba|a = a|b|aa = a|b|a|a.