ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

2044. 31 Palindromes

Time limit: 0.5 second
Memory limit: 64 MB
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.

Input

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

Output

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.

Sample

inputoutput
abaa
1
2
5
14

Notes

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