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

### Notes

1_{10} = 1_{2}; 2_{10} = 10_{2}; 5_{10} = 101_{2}; 14_{10} = 1110_{2};
*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