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.
110 = 12; 210 = 102; 510 = 1012; 1410 = 11102;
abaa = aba|a = a|b|aa = a|b|a|a.
Problem Author: Mikhail Rubinchik
Problem Source: Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014