ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Contest is over

## I. 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.

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
To submit the solution for this problem go to the Problem set: 2044. 31 Palindromes