Given a string, calculate for each position the length of the longest palindrome that ends at that position.

Input

The only line contains a string of length $n$. Each character is one of a–z.

Output

Print $n$ numbers: the length of each palindrome.

Constraints

• $1 \le n \le 2 \cdot 10^5$

Example

Input:

ababbababaa

Output:

1 1 3 3 2 4 6 8 5 5 2