Cho một xâu, hãy tính với mỗi vị trí độ dài của palindrome dài nhất kết thúc tại vị trí đó.

Input

Dòng duy nhất chứa một xâu độ dài \(n\). Mỗi ký tự là một trong các chữ cái a–z.

Output

In ra \(n\) số: độ dài của từng palindrome.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)

Example

ababbababaa

1 1 3 3 2 4 6 8 5 5 2