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

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

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

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