All Palindromes

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