Problem C. Compound palindrome

Author:A. Baranov   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  


A palindrome refers to a sequence of characters that reads the same in both directions (from left to right and from right to left).

A palindrome is compound if words of arbitrary length are used like characters.

It means that words located symmetrically from its center are the same.

Moreover, the words themselves do not have to be palindromes.

Consider a string, S, composed of digits and lowercase Latin alphabet letters.

The task is to split the original string into the maximum number of words,
ensuring that the resulting set is a compound palindrome.

Input format

The input consists of a single line, S.

Output format

The output should contain a sequence of word lengths, where the right ends of the words are located in the left half of the string.

If such a sequence does not exist, the output should remain empty.


1 ≤ |S| ≤ 2 ⋅ 106.

Sample tests

No. Standard input Standard output

0.068s 0.011s 13